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 after the rightmost x already there. Optio
(a, x, lo=0, hi=None, *, key=None)
| 17 | |
| 18 | |
| 19 | def bisect_right(a, x, lo=0, hi=None, *, key=None): |
| 20 | """Return the index where to insert item x in list a, assuming a is sorted. |
| 21 | |
| 22 | The return value i is such that all e in a[:i] have e <= x, and all e in |
| 23 | a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will |
| 24 | insert just after the rightmost x already there. |
| 25 | |
| 26 | Optional args lo (default 0) and hi (default len(a)) bound the |
| 27 | slice of a to be searched. |
| 28 | """ |
| 29 | |
| 30 | if lo < 0: |
| 31 | raise ValueError('lo must be non-negative') |
| 32 | if hi is None: |
| 33 | hi = len(a) |
| 34 | # Note, the comparison uses "<" to match the |
| 35 | # __lt__() logic in list.sort() and in heapq. |
| 36 | if key is None: |
| 37 | while lo < hi: |
| 38 | mid = (lo + hi) // 2 |
| 39 | if x < a[mid]: |
| 40 | hi = mid |
| 41 | else: |
| 42 | lo = mid + 1 |
| 43 | else: |
| 44 | while lo < hi: |
| 45 | mid = (lo + hi) // 2 |
| 46 | if x < key(a[mid]): |
| 47 | hi = mid |
| 48 | else: |
| 49 | lo = mid + 1 |
| 50 | return lo |
| 51 | |
| 52 | |
| 53 | def insort_left(a, x, lo=0, hi=None, *, key=None): |
no outgoing calls
no test coverage detected