Binary Search

# Binary Search

Zerethon Official Sample `binary-search`, version 1.5.0, Python 3.12.

- `binary_search.py` — the algorithm (`binary_search`, and `binary_search_steps` to trace it)
- `main.py` — entry file: searches a few values and prints the steps
- `test_binary_search.py` — checks; set it as the entry file to run them

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/binary-search-visualizer

"""Binary search over a sorted list (Zerethon Official Sample: binary-search 1.5.0)."""


def binary_search(a, target):
    """Return the index of target in a (sorted ascending), or -1 if it is absent."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def binary_search_steps(a, target):
    """Yield (lo, mid, hi) for every comparison binary_search makes."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        yield lo, mid, hi
        if a[mid] == target:
            return
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

from binary_search import binary_search, binary_search_steps

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("Sorted list:", numbers)
print()

for target in (23, 2, 91, 7):
    index = binary_search(numbers, target)
    result = f"found at index {index}" if index != -1 else "not found"
    print(f"search {target:>2}: {result}")

print()
print("Steps for 23 (lo, mid, hi):")
for lo, mid, hi in binary_search_steps(numbers, 23):
    print(f"  lo={lo} mid={mid} hi={hi} -> a[mid]={numbers[mid]}")

# Checks for binary_search. To run them, set this file as the entry file
# (the ▶ button next to it in Files) and press Run.
from binary_search import binary_search

cases = [
    ([], 1, -1),
    ([4], 4, 0),
    ([4], 5, -1),
    ([1, 3, 5, 7, 9], 1, 0),
    ([1, 3, 5, 7, 9], 9, 4),
    ([1, 3, 5, 7, 9], 6, -1),
    (list(range(0, 1000, 2)), 998, 499),
]

for a, target, expected in cases:
    got = binary_search(a, target)
    assert got == expected, f"binary_search({a[:5]}..., {target}) = {got}, expected {expected}"

print(f"All {len(cases)} checks passed.")