Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will insert just before the leftmost x already there. Optio
(a, x, lo=0, hi=None, *, key=None)
| 66 | a.insert(lo, x) |
| 67 | |
| 68 | def bisect_left(a, x, lo=0, hi=None, *, key=None): |
| 69 | """Return the index where to insert item x in list a, assuming a is sorted. |
| 70 | |
| 71 | The return value i is such that all e in a[:i] have e < x, and all e in |
| 72 | a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will |
| 73 | insert just before the leftmost x already there. |
| 74 | |
| 75 | Optional args lo (default 0) and hi (default len(a)) bound the |
| 76 | slice of a to be searched. |
| 77 | """ |
| 78 | |
| 79 | if lo < 0: |
| 80 | raise ValueError('lo must be non-negative') |
| 81 | if hi is None: |
| 82 | hi = len(a) |
| 83 | # Note, the comparison uses "<" to match the |
| 84 | # __lt__() logic in list.sort() and in heapq. |
| 85 | if key is None: |
| 86 | while lo < hi: |
| 87 | mid = (lo + hi) // 2 |
| 88 | if a[mid] < x: |
| 89 | lo = mid + 1 |
| 90 | else: |
| 91 | hi = mid |
| 92 | else: |
| 93 | while lo < hi: |
| 94 | mid = (lo + hi) // 2 |
| 95 | if key(a[mid]) < x: |
| 96 | lo = mid + 1 |
| 97 | else: |
| 98 | hi = mid |
| 99 | return lo |
| 100 | |
| 101 | |
| 102 | # Overwrite above definitions with a fast C implementation |
no outgoing calls
no test coverage detected