Why this random number guessing game simulation yielding ≈ 5.8

I have built this simple simulation that tries to beat the random number guessing game for a given times and records the moves.

import random
import time

def main():
    range_val = 1000000
    total_moves = 0
    
    random.seed(time.time())

    for i in range(range_val):
        target = random.randint(1, 100)

        low, high = 1, 100
        moves = 0
        guess = 0

        while low <= high:
            moves += 1
            guess = (low + high) // 2

            if guess == target:
                break
            elif guess < target:
                low = guess + 1
            else:
                high = guess - 1

        total_moves += moves

    print(float(total_moves) / float(range_val))

if __name__ == "__main__":
    main()

As the range_val is getting bigger I noticed the average moves required is approaching 5.8 or something near it. I don't have a solid reason to describe this. Why this specific number? Please help me with it.

Solution

Binary search algorithm

You are using a binary search algorithm in your simulation. You can visualize the algorithm as a binary tree:

The first attempt will always be 50 in your example. It is on the top of the binary tree. There is a 1 percent chance that the number you are looking for is actually 50. Therefore, there is a 1 percent chance of one attempt.
After that, the program will suggest either 25 or 75. These numbers are located in the second layer of the tree. And there is a 2 percent chance that the number you are looking for is 25 or 75. So there is a 2 percent chance of 2 attempts.

... and so on.

Why is 5.8 the result

This results in the following:

Attempts	Probability	Explanation
1	1.00%	The number 50 is found immediately.
2	2.00%	If the number is 25 or 75
3	4.00%	If the number is 12, 37, 62 or 87
4	8.00%	...
5	16.00%	...
6	32.00%	...
7	37.00%	...

Now if you multiply the number of attempts by the probability and add everything together:

1 * 0.01 +
2 * 0.02 + 
3 * 0.04 + 
4 * 0.08 +
5 * 0.16 +
6 * 0.32 +
7 * 0.37 = 5.8

you will get 5.8 as the result.

Conclusion

The reason why you don't get a nice even number is that 100 is not a power of 2. If you were to search in the range of 1 and 128, the result would be exactly 6.