Locates the first element in a sorted array that is larger than a given value. It has the same interface as https://docs.python.org/3/library/bisect.html#bisect.bisect_right . :param sorted_collection: some ascending sorted collection with comparable items :param item: item to
(
sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
)
| 57 | |
| 58 | |
| 59 | def bisect_right( |
| 60 | sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1 |
| 61 | ) -> int: |
| 62 | """ |
| 63 | Locates the first element in a sorted array that is larger than a given value. |
| 64 | |
| 65 | It has the same interface as |
| 66 | https://docs.python.org/3/library/bisect.html#bisect.bisect_right . |
| 67 | |
| 68 | :param sorted_collection: some ascending sorted collection with comparable items |
| 69 | :param item: item to bisect |
| 70 | :param lo: lowest index to consider (as in sorted_collection[lo:hi]) |
| 71 | :param hi: past the highest index to consider (as in sorted_collection[lo:hi]) |
| 72 | :return: index i such that all values in sorted_collection[lo:i] are <= item and |
| 73 | all values in sorted_collection[i:hi] are > item. |
| 74 | |
| 75 | Examples: |
| 76 | >>> bisect_right([0, 5, 7, 10, 15], 0) |
| 77 | 1 |
| 78 | >>> bisect_right([0, 5, 7, 10, 15], 15) |
| 79 | 5 |
| 80 | >>> bisect_right([0, 5, 7, 10, 15], 6) |
| 81 | 2 |
| 82 | >>> bisect_right([0, 5, 7, 10, 15], 15, 1, 3) |
| 83 | 3 |
| 84 | >>> bisect_right([0, 5, 7, 10, 15], 6, 2) |
| 85 | 2 |
| 86 | """ |
| 87 | if hi < 0: |
| 88 | hi = len(sorted_collection) |
| 89 | |
| 90 | while lo < hi: |
| 91 | mid = lo + (hi - lo) // 2 |
| 92 | if sorted_collection[mid] <= item: |
| 93 | lo = mid + 1 |
| 94 | else: |
| 95 | hi = mid |
| 96 | |
| 97 | return lo |
| 98 | |
| 99 | |
| 100 | def insort_left( |