# Principled Programming / Tim Teitelbaum / Chapter 8.
def find(A: list[int], v: int) -> int:
    """
    Assume A[0..n-1] is arranged in non-decreasing order.
    Let k be an index of A where A[k]==v, or n if no v in A.
    """

    n: int = len(A)
    L: int = 0; R : int = n - 1

    # Invariant: v is in A[L..R] if v is in A[0..n-1].
    # Variant: R-L.
    while L != R:
       M: int = (L+R) // 2
       if v <= A[M]:
           R = M
       else:
           L = M + 1
    k: int
    if n != 0 and A[L] == v: k = L;
    else: k = n
    return k

def e8_1_1():
    """Test Binary Search."""
    A: list[int] = [0,1,2,3,4,5,6,7,8,9,10]

    print("0 was found in", A, "at index",find(A, 0))
    print("1 was found in", A, "at index",find(A, 1))
    print("2 was found in", A, "at index",find(A, 2))
    print("3 was found in", A, "at index",find(A, 3))
    print("4 was found in", A, "at index",find(A, 4))
    print("5 was found in", A, "at index",find(A, 5))
    print("6 was found in", A, "at index",find(A, 6))
    print("7 was found in", A, "at index",find(A, 7))
    print("8 was found in", A, "at index",find(A, 8))
    print("9 was found in", A, "at index",find(A, 9))
    print("10 was found in", A, "at index",find(A, 10))

# Uncomment out to run.
#e8_1_1()