| 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 | ||||