Question

Write a program in python for this scenario :

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(10^10) − B(10^10) rounded to 8 decimal places

Answer 1

To solve this problem, we can simulate the binary search and the random binary search algorithms and calculate the expected number of guesses needed to find the secret integer t using each algorithm. We can repeat the simulation many times and take the average to get a good estimate of the expected number of guesses.

Here's the Python code to simulate the two algorithms and calculate the expected number of guesses:

import random

def binary_search(n):
L, H = 1, n
num_guesses = 0
while True:
num_guesses += 1
g = (L + H) // 2
if g == t:
return num_guesses
elif g < t:
L = g + 1
else:
H = g - 1

def random_binary_search(n):
L, H = 1, n
num_guesses = 0
while True:
num_guesses += 1
g = random.randint(L, H)
if g == t:
return num_guesses
elif g < t:
L = g + 1
else:
H = g - 1

n = 10**10
num_trials = 1000
diff_sum = 0
for i in range(num_trials):
t = random.randint(1, n)
diff_sum += random_binary_search(n) - binary_search(n)
print(round(diff_sum / num_trials, 8))

This code simulates the two algorithms 1000 times for n = 10^10, calculates the difference between the expected number of guesses for the random binary search and the standard binary search, and takes the average. The final output is rounded to 8 decimal places.

Note that running this code may take several minutes to complete because of the large value of n and the number of simulations