Number of guesses for various binary search strategies (random targets)

ev-guessing.py

import matplotlib.pyplot as plt
import numpy as np
import random
from math import log2

# Define the binary search strategies
def choose_straight_middle_left(left_incl, right_incl):
    return (left_incl + right_incl) // 2

def choose_straight_middle_right(left_incl, right_incl):
    return (left_incl + right_incl + 1) // 2

def choose_right_leaning(left_incl, right_incl):
    search_space_size = right_incl - left_incl + 1
    log_size = int(log2(search_space_size))
    return min(left_incl + 2 ** log_size - 1, right_incl)

def choose_left_leaning(left_incl, right_incl):
    search_space_size = right_incl - left_incl + 1
    log_size = int(log2(search_space_size))
    return max(left_incl, right_incl - 2 ** log_size + 1)

# Simulation parameters
iterations = 100  # number of random targets to test

# Initialize arrays to hold the number of guesses for each strategy
straight_middle_left_counts = []
straight_middle_right_counts = []
right_leaning_counts = []
left_leaning_counts = []

# Simulate for 'iterations' random target numbers
for _ in range(iterations):
    target = random.randint(1, 100)  # choose a random target number
    left_incl = 1
    right_incl = 100
    
    # Variables to count guesses for each strategy
    straight_middle_left_guess_count = 0
    straight_middle_right_guess_count = 0
    right_leaning_guess_count = 0
    left_leaning_guess_count = 0
    
    # Simulate for straight middle-left strategy
    left, right = left_incl, right_incl
    while left <= right:
        straight_middle_left_guess_count += 1
        guess = choose_straight_middle_left(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Simulate for straight middle-right strategy
    left, right = left_incl, right_incl
    while left <= right:
        straight_middle_right_guess_count += 1
        guess = choose_straight_middle_right(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Simulate for right-leaning strategy
    left, right = left_incl, right_incl
    while left <= right:
        right_leaning_guess_count += 1
        guess = choose_right_leaning(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Simulate for left-leaning strategy
    left, right = left_incl, right_incl
    while left <= right:
        left_leaning_guess_count += 1
        guess = choose_left_leaning(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Store the number of guesses for each strategy
    straight_middle_left_counts.append(straight_middle_left_guess_count)
    straight_middle_right_counts.append(straight_middle_right_guess_count)
    right_leaning_counts.append(right_leaning_guess_count)
    left_leaning_counts.append(left_leaning_guess_count)

# Plotting the results
iterations_range = np.arange(1, iterations + 1)

plt.figure(figsize=(10, 6))

# Plot each strategy's guess counts
plt.plot(iterations_range, straight_middle_left_counts, label="Middle Left", marker='o')
plt.plot(iterations_range, straight_middle_right_counts, label="Middle Right", marker='s')
plt.plot(iterations_range, right_leaning_counts, label="Right-Leaning", marker='^')
plt.plot(iterations_range, left_leaning_counts, label="Left-Leaning", marker='x')

# Add labels and title
plt.xlabel("Iteration (Random Target Number)")
plt.ylabel("Number of Guesses")
plt.title("Number of Guesses for Various Binary Search Strategies (Random Targets)")
plt.legend()

# Display the plot
plt.grid(True)
plt.show()