A secret integer is selected at random within the range .
The goal is to guess the value of by making repeated guesses, via integer . After a guess is made, there are three possible outcomes, in which it will be revealed that either , , or . Then the process can repeat as necessary.
Normally, the number of guesses required on average can be minimized with a binary search: Given a lower bound and upper bound (initialized to and ), let where is the integer floor function. If , the process ends. Otherwise, if , set , but if instead, set . After setting the new bounds, the search process repeats, and ultimately ends once is found. Even if can be deduced without searching, assume that a search will be required anyway to confirm the value.
Your friend Bob believes that the standard binary search is not that much better than his randomized variant: Instead of setting , simply let be a random integer between and , inclusive. The rest of the algorithm is the same as the standard binary search. This new search routine will be referred to as a random binary search.
Given that for random , let be the expected number of guesses needed to find using the standard binary search, and let be the expected number of guesses needed to find using the random binary search. For example, and when rounded to decimal places.
Find rounded to decimal places.