"""Chaper 3.3, exercise 3.

Write a function called bisection that takes a sorted list and a target value
and returns the index of the value in the list if it's there, or None if it's
not.

"""

def bisection(a, item):
    """Returns the index of item in the sorted list a if it exists or None if
    not.

    Finds the "rightmost" item if it exists.

    """
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2
        if item < a[mid]:
            hi = mid
        else:
            lo = mid + 1

    n = lo - 1
    return n if n >= 0 and a[n] == item else None


if __name__ == '__main__':
    a = [0, 2, 4, 5, 7, 22]

    assert bisection(a, 0) == 0
    assert bisection(a, 22) == len(a) - 1
    assert bisection(a, 4) == 2