for_vs_binary.py

import numpy as np
import bisect
import timeit
import matplotlib.pyplot as plt

# Initialize list to store results
results = []

# Test for different array sizes
test_values = [1000, 10000, 100000, 1000000, 10000000, 100000000]

for n in test_values:
    # Prepare the sorted array
    arr = np.random.randint(0, n * 10, n)
    sorted_arr = np.sort(arr)
    index = np.random.randint(0, len(sorted_arr))
    lookup_value = sorted_arr[index]

    # Measure time for a for-loop search
    time_for_loop = timeit.timeit(
        stmt="""for i in range(len(sorted_arr)):
    if sorted_arr[i] == lookup_value:
        break""",
        globals={"sorted_arr": sorted_arr, "lookup_value": lookup_value},
        number=1  # Run once for each test
    )

    # Measure time for bisect.bisect_left search
    time_bisect = timeit.timeit(
        stmt="bisect.bisect_left(sorted_arr, lookup_value)",
        globals={"sorted_arr": sorted_arr, "lookup_value": lookup_value, "bisect": bisect},
        number=1
    )

    # Measure time for np.searchsorted
    time_np_searchsorted = timeit.timeit(
        stmt="np.searchsorted(sorted_arr, lookup_value)",
        globals={"sorted_arr": sorted_arr, "lookup_value": lookup_value, "np": np},
        number=1
    )

    # Store results as a tuple
    results.append((n, time_for_loop, time_bisect, time_np_searchsorted))
    print(f"n={n}, time_for_loop={time_for_loop:.6f}s, "
          f"time_bisect={time_bisect:.6f}s, "
          f"time_np_searchsorted={time_np_searchsorted:.6f}s")

# Plot the results
n_values, times_for_loop, times_bisect, times_np_searchsorted = zip(*results)

plt.figure(figsize=(10, 6))
plt.plot(n_values, times_for_loop, label="For Loop Search", marker='o')
plt.plot(n_values, times_bisect, label="Bisect Search", marker='o')
plt.plot(n_values, times_np_searchsorted, label="NumPy SearchSorted", marker='o')
plt.xscale("log")
plt.yscale("log")
plt.xlabel("Array Size (n)")
plt.ylabel("Time (seconds)")
plt.title("Performance: For Loop vs Bisect vs NumPy SearchSorted")
plt.legend()
plt.grid(True)
plt.show()