Guido van Rossum | 4e16098 | 1992-09-02 20:43:20 +0000 | [diff] [blame] | 1 | # Bisection algorithms |
2 | |||||
3 | |||||
4 | # Insert item x in list a, and keep it sorted assuming a is sorted | ||||
5 | |||||
6 | def insort(a, x): | ||||
7 | lo, hi = 0, len(a) | ||||
8 | while lo < hi: | ||||
9 | mid = (lo+hi)/2 | ||||
10 | if x < a[mid]: hi = mid | ||||
11 | else: lo = mid+1 | ||||
12 | a.insert(lo, x) | ||||
13 | |||||
14 | |||||
15 | # Find the index where to insert item x in list a, assuming a is sorted | ||||
16 | |||||
17 | def bisect(a, x): | ||||
18 | lo, hi = 0, len(a) | ||||
19 | while lo < hi: | ||||
20 | mid = (lo+hi)/2 | ||||
21 | if x < a[mid]: hi = mid | ||||
22 | else: lo = mid+1 | ||||
23 | return lo |