bgneal@11: """Chaper 3.3, exercise 3.
bgneal@11: 
bgneal@11: Write a function called bisection that takes a sorted list and a target value
bgneal@11: and returns the index of the value in the list if it's there, or None if it's
bgneal@11: not.
bgneal@11: 
bgneal@11: """
bgneal@11: 
bgneal@11: def bisection(a, item):
bgneal@11:     """Returns the index of item in the sorted list a if it exists or None if
bgneal@11:     not.
bgneal@11: 
bgneal@11:     Finds the "rightmost" item if it exists.
bgneal@11: 
bgneal@11:     """
bgneal@11:     lo = 0
bgneal@11:     hi = len(a)
bgneal@11: 
bgneal@11:     while lo < hi:
bgneal@11:         mid = (lo + hi) // 2
bgneal@11:         if item < a[mid]:
bgneal@11:             hi = mid
bgneal@11:         else:
bgneal@11:             lo = mid + 1
bgneal@11: 
bgneal@11:     n = lo - 1
bgneal@33:     return n if n >= 0 and a[n] == item else None
bgneal@33: 
bgneal@33: 
bgneal@33: if __name__ == '__main__':
bgneal@33:     a = [0, 2, 4, 5, 7, 22]
bgneal@33: 
bgneal@33:     assert bisection(a, 0) == 0
bgneal@33:     assert bisection(a, 22) == len(a) - 1
bgneal@33:     assert bisection(a, 4) == 2