Lower Bound Binary Search

Implement a classic lower_bound search that finds the first index where a value is not less than the target.

binary-search search arrays

Write a function `lower_bound(arr, target)` that takes a sorted list of integers `arr` (non-decreasing) and an integer `target`. It must return the index of the first element in `arr` that is **not less than** `target` (i.e., the smallest index `i` such that `arr[i] >= target`). If every element is less than `target`, return the length of `arr`. The algorithm must run in O(log n) time. Do not use built-in functions like `bisect`.

Constraints

0 <= len(arr) <= 10^5
-10^9 <= arr[i], target <= 10^9
arr is sorted in non-decreasing order.

Example

>>> lower_bound([1, 2, 3, 4], 3)
2
>>> lower_bound([1, 2, 3, 4], 5)
4
>>> lower_bound([1, 2, 3, 4], 0)
0
>>> lower_bound([], 5)
0

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about maintaining two boundaries: one where the answer is known to be to the right, and one where it is known to be to the left.

When the middle element is less than the target, you can safely discard everything up to and including it.

When the middle element is greater or equal, you can keep it as a candidate, but narrow the search to the left.

At the end, the boundary will point to the correct index.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.