"""Experiment 2: find a number in a sorted list, two ways.

Steps = how many items we look at. We search for the last item,
which is the worst case for checking every item from the start.
"""
from common import save

SIZES = [16, 1_000, 1_000_000]


def check_every_item(items, target):
    steps = 0
    for item in items:
        steps += 1
        if item == target:
            return steps
    return steps


def halving(items, target):
    lo, hi = 0, len(items) - 1
    steps = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        steps += 1
        if items[mid] == target:
            return steps
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps


results = []
print(f"{'items':>12} | {'check every item':>16} | {'halving':>8}")
for n in SIZES:
    items = list(range(1, n + 1))  # already sorted
    target = items[-1]
    linear = check_every_item(items, target)
    half = halving(items, target)
    print(f"{n:>12,} | {linear:>16,} | {half:>8}")
    results.append({"n": n, "target": target, "linear_steps": linear, "halving_steps": half})

save("exp2", results)