"""Test first-occurrence binary search against a linear reference."""

from itertools import combinations_with_replacement


def first_index(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if lo < len(values) and values[lo] == target:
        return lo
    return None


def linear_reference(values, target):
    return next((index for index, value in enumerate(values) if value == target), None)


if __name__ == "__main__":
    count = 0
    for length in range(8):
        for values in combinations_with_replacement(range(-2, 3), length):
            for target in range(-3, 4):
                expected = linear_reference(values, target)
                actual = first_index(values, target)
                assert actual == expected, (values, target, expected, actual)
                count += 1
    assert count == 5544
    print(f"Compared {count:,} input/target pairs.")
