"""
Exercise 1: First Bad Version (LeetCode 278)

Versions 1..n; once a version is bad, every later version is bad.
is_bad(v) tells you whether v is bad. Return the first bad version using
as few calls as possible (O(log n)).

The self-check counts your calls: it must be at most 40 for n = 2**31 - 1.
"""

def first_bad_version(n, is_bad):
    # TODO: binary search for the first True
    pass


# --- self-check: do not modify below this line ---
ok = True
for n, bad in [(5, 4), (1, 1), (2**31 - 1, 1702766719), (10, 1), (10, 10)]:
    calls = [0]
    def is_bad(v, bad=bad):
        calls[0] += 1
        return v >= bad
    got = first_bad_version(n, is_bad)
    print(f"n={n} first bad={bad} -> {got} ({calls[0]} calls)")
    ok = ok and got == bad and calls[0] <= 40
print("PASS" if ok else "FAIL")