You are given a sorted array arr (0-based indexing, non-decreasing order — duplicates allowed) and a number target.
Return the lower bound of target in arr: the smallest index i such that arr[i] >= target.
If every element of arr is strictly smaller than target, return arr.length — the position just past the end, where target would have to be appended to keep the array sorted.
target would be inserted to keep the array sorted — the first index holding a value >= target.n. The target would have to be appended at the end, so its insertion point is one past the last index.>= comparison plus the hi = mid move guarantees.arr[i] >= target; upper bound finds the first index with arr[i] > target. They differ only in the comparison, and their difference counts the occurrences of target.arr[mid] >= target to arr[mid] > target — everything else stays identical. It returns the first index strictly greater than the target.upperBound(arr, target) - lowerBound(arr, target). Two binary searches, about 40 probes total on a million elements.std::lower_bound, Python has bisect.bisect_left, Go has sort.SearchInts. Say so, then offer to implement it by hand; interviewers usually want the hand-rolled boundary search.std::lower_bound, Python's bisect_left, and Go's sort.Search all use exactly this first-YES boundary search.lo < hi / hi = mid template generalizes far beyond arrays — it powers binary search on the answer in problems like Koko Eating Bananas and Allocate Minimum Pages, where the yes/no question is a feasibility check instead of a comparison.Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 9 Output: 3 Index 3 is the smallest index where the element (arr[3] = 10) is greater than or equal to 9.
Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 11 Output: 4 Index 4 holds the first 11 — the smallest index with an element greater than or equal to 11.
Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 100 Output: 7 No element is greater than or equal to 100, so the answer is the array length, 7.
- 1 <= arr.size <= 10^6 - 1 <= arr[i] <= 10^6 - 1 <= target <= 10^6 - arr is sorted in non-decreasing order
Lower bound is the quiet workhorse of sorted-array problems: it powers the standard-library search in nearly every language, and it teaches the single most reusable binary-search pattern — finding the boundary where a condition flips from no to yes. Master it here and a dozen harder problems become one-liners.
[lo, hi) where hi starts one past the last index — the trick that lets the answer be n itself.In plain English: given a sorted arr and a target, return the smallest index i with arr[i] >= target. If no such index exists, return arr.length. Formally, it is the insertion point that keeps the array sorted while placing target before any equal elements.
Worked example — arr = [2, 3, 7, 10, 11, 11, 25], target = 9
index: 0 1 2 3 4 5 6
value: 2 3 7 10 11 11 25
<9 <9 <9 >=9 >=9 >=9 >=9
^
first index with value >= 9 → answer: 3
With target = 11 the answer is 4 — the first 11, not the second. With target = 100 nothing qualifies, so the answer is 7, the array length.
Two or three sharp questions before coding show an interviewer you think about contracts, not just code.
“Is the array guaranteed sorted, and can it contain duplicates?”
Yes and yes. Sortedness is what makes binary search legal; duplicates mean you must return the first index of an equal run, not just any match.
“Does the target have to exist in the array?”
No. Lower bound is defined even when the target is absent — it is the index where the target would be inserted to keep the array sorted.
“What do I return if every element is smaller than the target?”
The array length n — one past the last index. This is why the search range must include n as a candidate answer.
“What if the target is smaller than every element?”
Index 0 — the target would slot in at the very front.
“How large can the array be?”
Up to a million elements. A linear scan is about 10^6 checks — survivable once, but the expected answer is O(log n), roughly 20 probes.
Before I code, let me confirm: the array is sorted non-decreasing and may contain duplicates, right?
And the target may be absent — in that case I return the index where it would be inserted, which is the array length if everything is smaller.
Since the array is sorted and n can reach a million, I will binary search for the first element that is greater than or equal to the target.
Ask every element one question: is arr[i] >= target? Because the array is sorted, the answers read NO NO NO YES YES YES — all the NOs first, then all the YESes, never mixed. The lower bound is exactly the index of the first YES (or n if the YES zone is empty).
arr: 2 3 7 10 11 11 25 target = 9
ask: NO NO NO YES YES YES YES
^ first YES = lower bound = 3Probe the middle of the range. If arr[mid] >= target, then mid is a valid answer and so is everything to its right — remember it and search left for something earlier (hi = mid). If arr[mid] < target, then mid and everything to its left are useless — discard them (lo = mid + 1). Each probe halves the range.
The answer can be n itself (target bigger than everything). Searching the half-open range [0, n) with hi starting at n makes that case fall out naturally: if no element ever satisfies the condition, lo climbs all the way to n and that is what you return.
| Linear scan | Binary search | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
Both approaches, in all four languages, are in the Approaches selector below.
Key takeaway
Lower bound is the first-YES pattern: binary search not for a value but for the boundary where a monotonic condition (arr[i] >= target) flips from NO to YES. Keep every YES as a live candidate and push left; return lo when the window closes. The same template solves search-insert, first occurrence, and every answer-on-a-monotonic-predicate problem.
lo = 0, hi = n # half-open window [lo, hi)
while lo < hi:
mid = lo + (hi - lo) / 2
if arr[mid] >= target: hi = mid # mid works — try to go left
else: lo = mid + 1 # mid fails — discard left half
return lo