Mercurial > public > think_complexity

comparison ch3ex3.py @ 11:0f98bcb5bd3f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added the bisection() function for Ch 3.3 exercise 3.
author Brian Neal <bgneal@gmail.com>
date Mon, 10 Dec 2012 19:25:20 -0600
parents
children cfb7f28678c7
comparison
equal deleted inserted replaced
10:aea27d10dd18 11:0f98bcb5bd3f
1 """Chaper 3.3, exercise 3.
2
3 Write a function called bisection that takes a sorted list and a target value
4 and returns the index of the value in the list if it's there, or None if it's
5 not.
6
7 """
8
9 def bisection(a, item):
10 """Returns the index of item in the sorted list a if it exists or None if
11 not.
12
13 Finds the "rightmost" item if it exists.
14
15 """
16 lo = 0
17 hi = len(a)
18
19 while lo < hi:
20 mid = (lo + hi) // 2
21 if item < a[mid]:
22 hi = mid
23 else:
24 lo = mid + 1
25
26 n = lo - 1
27 return a[n] if n >= 0 and a[n] == item else None