think_complexity: ch3ex3.py annotate

Added the bisection() function for Ch 3.3 exercise 3.

rev	line source
bgneal@11	1 """Chaper 3.3, exercise 3.
bgneal@11	2
bgneal@11	3 Write a function called bisection that takes a sorted list and a target value
bgneal@11	4 and returns the index of the value in the list if it's there, or None if it's
bgneal@11	5 not.
bgneal@11	6
bgneal@11	7 """
bgneal@11	8
bgneal@11	9 def bisection(a, item):
bgneal@11	10 """Returns the index of item in the sorted list a if it exists or None if
bgneal@11	11 not.
bgneal@11	12
bgneal@11	13 Finds the "rightmost" item if it exists.
bgneal@11	14
bgneal@11	15 """
bgneal@11	16 lo = 0
bgneal@11	17 hi = len(a)
bgneal@11	18
bgneal@11	19 while lo < hi:
bgneal@11	20 mid = (lo + hi) // 2
bgneal@11	21 if item < a[mid]:
bgneal@11	22 hi = mid
bgneal@11	23 else:
bgneal@11	24 lo = mid + 1
bgneal@11	25
bgneal@11	26 n = lo - 1
bgneal@11	27 return a[n] if n >= 0 and a[n] == item else None

Mercurial > public > think_complexity