Find the Lower Bound of a Target in a Sorted Array
Solve this Problem
Given an array
nums sorted in non-decreasing order (duplicates allowed) and an integer target, return its lower bound — the index of the first element that is greater than or equal to target. If every element is smaller, return nums.length.
This is one of the most useful binary-search building blocks: many harder problems (counting occurrences, finding a range, floor/ceil) are just a lower bound and an upper bound combined.
Test Case 1:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 5
Output:2
Explanation:Index 2 is the first position whose value is ≥ 5.
Test Case 2:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 4
Output:2
Explanation:4 isn't present, but index 2 (value 5) is still the first value ≥ 4.
Test Case 3:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 10
Output:7
Explanation:Nothing is ≥ 10, so the bound sits one past the last index.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁴ - ◆
-10⁴ ≤ nums[i], target ≤ 10⁴ - ◆
nums is sorted in non-decreasing order (duplicates are allowed)
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int lowerBound(int[] nums, int target) { |
| 3 | int lo = 0, hi = nums.length - 1, ans = nums.length; |
| 4 | while (lo <= hi) { |
| 5 | int mid = lo + (hi - lo) / 2; |
| 6 | if (nums[mid] >= target) { |
| 7 | ans = mid; |
| 8 | hi = mid - 1; |
| 9 | } else { |
| 10 | lo = mid + 1; |
| 11 | } |
| 12 | } |
| 13 | return ans; |
| 14 | } |
| 15 | } |
| 16 |
1
3
5
5
5
7
9
0
1
2
3
4
5
6
↑lo
↑hi
Variables
lo
0hi
6ans
7INITIALIZE
Search [0, 6] for the leftmost index where nums[i] ≥ 5. Default ans to 7 (past the end) until something qualifies.
Step 1 / 5
Approach & Solutions
Brute Force — Linear Scan
BruteWalk left to right and return the first index whose value is ≥ target. It's correct on any array, sorted or not, but it never uses the sortedness that lets binary search skip most of the comparisons.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int lowerBound(int[] nums, int target) {
3 for (int i = 0; i < nums.length; i++) {
4 if (nums[i] >= target) return i;
5 }
6 return nums.length;
7 }
8}Optimal — Binary Search
OptimalThe lower bound is the leftmost index whose value is ≥ target. Whenever nums[mid] ≥ target, mid is a valid candidate — record it and keep searching left for an even earlier one. Otherwise the answer must be further right.
Time
O(log n)Space
O(1)Java
1class Solution {
2 public int lowerBound(int[] nums, int target) {
3 int lo = 0, hi = nums.length - 1, ans = nums.length;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 if (nums[mid] >= target) {
7 ans = mid;
8 hi = mid - 1;
9 } else {
10 lo = mid + 1;
11 }
12 }
13 return ans;
14 }
15}