| 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 | |
| Guido van Rossum | d5484fb | 1997-10-07 14:45:49 +0000 | [diff] [blame] | 6 | def insort(a, x, lo=0, hi=None): |
| 7 | if hi is None: |
| 8 | hi = len(a) |
| Guido van Rossum | 8ca8420 | 1998-03-26 20:56:10 +0000 | [diff] [blame] | 9 | while lo < hi: |
| Guido van Rossum | 4e16098 | 1992-09-02 20:43:20 +0000 | [diff] [blame] | 10 | mid = (lo+hi)/2 |
| 11 | if x < a[mid]: hi = mid |
| 12 | else: lo = mid+1 |
| 13 | a.insert(lo, x) |
| 14 | |
| 15 | |
| 16 | # Find the index where to insert item x in list a, assuming a is sorted |
| 17 | |
| Guido van Rossum | d5484fb | 1997-10-07 14:45:49 +0000 | [diff] [blame] | 18 | def bisect(a, x, lo=0, hi=None): |
| 19 | if hi is None: |
| 20 | hi = len(a) |
| Guido van Rossum | 8ca8420 | 1998-03-26 20:56:10 +0000 | [diff] [blame] | 21 | while lo < hi: |
| Guido van Rossum | 4e16098 | 1992-09-02 20:43:20 +0000 | [diff] [blame] | 22 | mid = (lo+hi)/2 |
| 23 | if x < a[mid]: hi = mid |
| 24 | else: lo = mid+1 |
| 25 | return lo |