think_complexity: ch3ex3.py annotate

Got a first draft Turing Machine working for chapter 6, exercise 4. Next I have to figure out how to draw it with a TMDrawer class.

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@33	27 return n if n >= 0 and a[n] == item else None
bgneal@33	28
bgneal@33	29
bgneal@33	30 if __name__ == '__main__':
bgneal@33	31 a = [0, 2, 4, 5, 7, 22]
bgneal@33	32
bgneal@33	33 assert bisection(a, 0) == 0
bgneal@33	34 assert bisection(a, 22) == len(a) - 1
bgneal@33	35 assert bisection(a, 4) == 2

Mercurial > public > think_complexity