Write lower_bound(a: list[int], x: int) -> int that returns the first index i with a[i] >= x. If every element is smaller than x, return len(a). a is sorted in non-decreasing order and may contain duplicates.
It's also the position where x would be inserted to keep a sorted, before any equal values.
a = [1, 3, 3, 3, 8]
lower_bound(a, 3) # 1 (the first 3)
lower_bound(a, 4) # 4 (8 is the first value >= 4)
lower_bound(a, 0) # 0
lower_bound(a, 9) # 5 (= len(a))
0 <= len(a) <= 10^6; the tests make thousands of calls on one big list, so it must be O(log n).- Don't use the
bisectmodule orlist.index; the point is to write the loop. - C++ / Java: you write
lowerBoundAll(a, xs), which returnslower_bound(a, x)for everyxinxs, in order, so the tests can run many searches on one big list. WritelowerBoundas a helper and call it in a loop.
Show hint
keep a half-open range [lo, hi) that always contains the answer, starting with lo, hi = 0, len(a); if a[mid] < x the answer is after mid (lo = mid + 1), otherwise mid itself might be it (hi = mid), and you stop when lo == hi.