| Guido van Rossum | 4acc25b | 2000-02-02 15:10:15 +0000 | [diff] [blame] | 1 | """Bisection algorithms.""" |
| Guido van Rossum | 4e16098 | 1992-09-02 20:43:20 +0000 | [diff] [blame] | 2 | |
| 3 | |
| Guido van Rossum | d5484fb | 1997-10-07 14:45:49 +0000 | [diff] [blame] | 4 | def insort(a, x, lo=0, hi=None): |
| Guido van Rossum | 4acc25b | 2000-02-02 15:10:15 +0000 | [diff] [blame] | 5 | """Insert item x in list a, and keep it sorted assuming a is sorted.""" |
| 6 | if hi is None: |
| 7 | hi = 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) |
| Guido van Rossum | 4e16098 | 1992-09-02 20:43:20 +0000 | [diff] [blame] | 13 | |
| 14 | |
| Guido van Rossum | d5484fb | 1997-10-07 14:45:49 +0000 | [diff] [blame] | 15 | def bisect(a, x, lo=0, hi=None): |
| Guido van Rossum | 4acc25b | 2000-02-02 15:10:15 +0000 | [diff] [blame] | 16 | """Find the index where to insert item x in list a, assuming a is sorted.""" |
| 17 | if hi is None: |
| 18 | hi = 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 |