Problem 527
Randomized Binary Search
A secret integer t is selected at random within the range 1 ≤ t ≤ n.
The goal is to guess the value of t by making repeated guesses, via integer g. After a guess is made, there are three possible outcomes, in which it will be revealed that either g < t, g = t, or g > t. 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 L and upper bound H (initialized to L = 1 and H = n), let g = ⌊(L+H)/2⌋ where ⌊⋅⌋ is the integer floor function. If g = t, the process ends. Otherwise, if g < t, set L = g+1, but if g > t instead, set H = g−1. After setting the new bounds, the search process repeats, and ultimately ends once t is found. Even if t 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 g = ⌊(L+H)/2⌋, simply let g be a random integer between L and H, 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 1 ≤ t ≤ n for random t, let B(n) be the expected number of guesses needed to find t using the standard binary search, and let R(n) be the expected number of guesses needed to find t using the random binary search. For example, B(6) = 2.33333333 and R(6) = 2.71666667 when rounded to 8 decimal places.
Find R(1010) − B(1010) rounded to 8 decimal places.
随机二分查找
在1 ≤ t ≤ n的范围中，随机选择一个整数t作为秘密整数。
我们要通过不断地猜测整数g来得知t的值。每次猜测会有三种可能的反馈，要么g < t，要么g = t，要么g > t。如果没有猜中，则继续进行下一次猜测。
一般而言，二分搜索可以最小化猜测的次数：给定下界为L，上界为H（初始情况下L = 1而H = n），则猜测 g =⌊(L+H)/2⌋，其中⌊⋅⌋为下取整函数。如果g = t，则猜测结束。否则，若g < t，则令L = g+1，若g > t，则令H = g−1。重新设定上下界后，继续进行下一次猜测，直到找出t的值。我们约定，即使不需要再猜一次也已经知道t的值，仍然必须再猜一次进行确认。
你的朋友鲍勃相信标准的二分查找比他的随机方法好不到哪儿去：他并不猜测 g = ⌊(L+H)/2⌋，而是随机地猜测L和H之间的一个整数。算法的剩余部分和标准二分查找并无不同。这种新方法被称为随机二分查找。
在1 ≤ t ≤ n中任取整数t，记B(n)为使用标准二分查找找出t所需猜测的期望次数，记R(n)为使用随机二分查找找出t所需猜测的期望次数。例如，B(6) = 2.33333333而R(6) = 2.71666667，均四舍五入到8位小数。
求R(1010) − B(1010)并四舍五入到8位小数。