15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Lower bound is the first index i where A[i] >= target in a nondecreasing array. Upper bound is the first index where A[i] > target. Both search the half-open interval [low, high) and keep mid when the test is true. Each takes O(log n) time, and together they give the first and last occurrence of a value.
| Lower bound | First index with A[i] >= target, or n if none |
|---|---|
| Upper bound | First index with A[i] > target, or n if none |
| Range of a value | [lower, upper), first = lower, last = upper - 1 |
| Initial interval | [0, n), so the answer can be n |
| Time and space | O(log n) time, O(1) extra space per search |
| Absent target | Lower bound is the insertion index |
Assume you can already do an exact-match binary search on a sorted array.
Here, the array is nondecreasing: equal values may appear next to each other.
Instead of asking, “Did I find one copy of the target?” ask boundary questions:
i where A[i] >= target.i where A[i] > target.The definitions also give insertion positions when the target is absent.
Use a half-open search interval:
1[low, high)It includes low and excludes high. For an array of length n, the possible insertion indices are 0 through n, so start with:
1low = 0
2high = nThe array is not modified by any operation in this lesson.
Reference material for ordered-array binary-search operations: Algorithms, 4th edition companion site.
Write the array with its indices.
1index: 0 1 2 3 4
2A: [1, 3, 3, 3, 5]
3
4target = 3Find the lower bound of 3: the first index whose value is at least 3.
The answer is index 1. Indices 2 and 3 also contain 3, but neither is the first legal position.
At the start, every insertion index is possible.
1[low, high) = [0, 5)The candidate interval contains indices where the boundary might still be. It may eventually become empty. When low == high, that shared index is the answer.
For lower bound, equality uses the “move left” case.
Lower bound of 3 in [1, 3, 3, 3, 5]: [0, 5) to [0, 2) to [0, 1) to [1, 1), so the lower bound is 1. The upper bound is 4, so all copies of 3 fill [1, 4).
If A[mid] >= target, then mid might be the first valid index. A smaller valid index might also exist, so keep the left side and exclude mid from the right boundary:
1high = midIf A[mid] < target, then mid cannot be the lower bound. Neither can anything to its left, because the array is nondecreasing:
1low = mid + 1Follow the exact states.
| State | Candidate interval | Midpoint | Value at midpoint | Decision | Next interval |
|---|---|---|---|---|---|
| 0 | [0, 5) | 2 | A[2] = 3 | 3 >= 3, so keep earlier candidates | [0, 2) |
| 1 | [0, 2) | 1 | A[1] = 3 | 3 >= 3, so keep earlier candidates | [0, 1) |
| 2 | [0, 1) | 0 | A[0] = 1 | 1 < 3, so index 0 cannot work | [1, 1) |
| 3 | [1, 1) | — | — | low == high; stop | lower bound is 1 |
The equal values at indices 2 and 1 do not end the search. Each update moves high left because a first occurrence could still be earlier.
For upper bound, change only the comparison:
A[mid] >= target.A[mid] > target.For the same array and target:
1lower bound = 1
2upper bound = 4All copies of 3 occupy:
1[lower bound, upper bound) = [1, 4)The first occurrence is 1. The last occurrence is:
1upper bound - 1 = 3During lower-bound search:
low is definitely too small.high is definitely large enough.[low, high).The loop invariant is:
Every index below
lowhas value less than the target, every index at or abovehighhas value at least the target, and the answer is in[low, high).
Look at State 1:
1[low, high) = [0, 2)0 is below low only after the next update; it has value 1, which is less than 3.2, 3, and 4 are at or above the earlier high boundary 2; their values are at least 3.1, remains in the candidate interval.Duplicates do not break this rule. When A[mid] == target, mid is valid, but it may not be the first valid index. Moving high to mid preserves the possibility of finding an earlier equal value.
For upper bound:
low has value at most the target.high has value greater than the target.[low, high).Start with all possible insertion positions:
1low = 0
2high = nAs long as candidates remain, calculate a midpoint inside [low, high):
1mid = low + floor((high - low) / 2)Because mid < high, A[mid] is a valid array access while low < high.
For lower bound:
A[mid] >= target, mid is a legal position or lies after one.mid can be earlier than mid.high = mid.Otherwise:
A[mid] < target.mid cannot be the first index whose value is at least the target.mid and everything before it with low = mid + 1.For upper bound, test A[mid] > target. Set high = mid when the test is true. Otherwise set low = mid + 1.
Once you have both bounds:
lower < n and A[lower] == target.first = lower.upper - 1.[-1, -1].For an absent target, lower bound is also the insertion index. For example:
1A = [1, 2, 4], target = 3
2lower bound = 2Inserting 3 at index 2 keeps the array nondecreasing.
All functions below take a nondecreasing array A. None mutates A.
lowerBoundA of length n, value targeti in 0..n such that A[i] >= target; returns n if no array value is at least targetA[low, high)11 function lowerBound(A, target):
22 n = length(A)
33 low = 0
44 high = n
55
66 while low < high:
77 mid = low + floor((high - low) / 2)
88
99 if A[mid] >= target:
1010 high = mid
1111 else:
1212 low = mid + 1
1313
1414 return lowupperBoundA of length n, value targeti in 0..n such that A[i] > target; returns n if no array value is greater than targetA[low, high)11 function upperBound(A, target):
22 n = length(A)
33 low = 0
44 high = n
55
66 while low < high:
77 mid = low + floor((high - low) / 2)
88
99 if A[mid] > target:
1010 high = mid
1111 else:
1212 low = mid + 1
1313
1414 return lowfirstAndLastOccurrenceA, value target[first, last] when target occurs; otherwise [-1, -1]AlowerBound and upperBound satisfy the contracts above11 function firstAndLastOccurrence(A, target):
22 lower = lowerBound(A, target)
33
44 if lower == length(A) or A[lower] != target:
55 return [-1, -1]
66
77 upper = upperBound(A, target)
88 return [lower, upper - 1]Dry-run lowerBound(A, 3) using the original array.
1index: 0 1 2 3 4
2A: [1, 3, 3, 3, 5]| Pseudocode line | Variables or test | Result |
|---|---|---|
| 2 | n = length(A) | n = 5 |
| 3 | low = 0 | low = 0 |
| 4 | high = n | high = 5 |
| 6 | low < high | 0 < 5, enter loop |
| 7 | mid = 0 + floor((5 - 0) / 2) | mid = 2 |
| 9 | A[2] >= 3 | 3 >= 3 is true |
| 10 | high = mid | high = 2; interval is [0, 2) |
| 6 | low < high | 0 < 2, enter loop |
| 7 | mid = 0 + floor((2 - 0) / 2) | mid = 1 |
| 9 | A[1] >= 3 | 3 >= 3 is true |
| 10 | high = mid | high = 1; interval is [0, 1) |
| 6 | low < high | 0 < 1, enter loop |
| 7 | mid = 0 + floor((1 - 0) / 2) | mid = 0 |
| 9 | A[0] >= 3 | 1 >= 3 is false |
| 12 | low = mid + 1 | low = 1; interval is [1, 1) |
| 6 | low < high | 1 < 1 is false; exit loop |
| 14 | return low | return 1 |
The returned index is 1, the first occurrence of 3.
For the same input, upperBound(A, 3) returns 4. Therefore:
1firstAndLastOccurrence(A, 3)
2= [1, 4 - 1]
3= [1, 3]Let the required answer be the first insertion position whose value is at least target. This position can be from 0 through n.
Initialization
Before the loop:
1low = 0
2high = nNo index is below low, so the statement “every index below low is less than the target” is true.
No index is at or above high within the array, so the statement about those indices is also true.
Every possible insertion position lies in [0, n]. Thus the answer is covered by [low, high].
Preservation when A[mid] >= target
Set:
1high = midBecause the array is nondecreasing and A[mid] >= target, every index from mid onward has value at least target.
No index at or after mid can be earlier than the answer. The answer remains in [low, mid). The invariant is preserved.
Preservation when A[mid] < target
Set:
1low = mid + 1Index mid is too small to be the answer. Since the array is nondecreasing, every index before mid is also too small.
Every index below the new low has value less than the target. The answer remains in [mid + 1, high). The invariant is preserved.
Termination
The loop stops when:
1low == highThe candidate interval has no remaining width. By the invariant:
low is too small;high, which equals low, is at least the target.Therefore low is exactly the first legal insertion position. The function returns the lower bound.
For upperBound, replace “at least the target” with “greater than the target.” The A[mid] > target branch sets high = mid, and the other branch sets low = mid + 1.
For occurrence reporting, the lower bound alone does not prove that a target exists. The algorithm checks:
1lower < length(A) and A[lower] == targetIf this check fails, no occurrence exists, so [-1, -1] is correct.
If it succeeds:
lower is the first occurrence because it is the first index with value at least target;upper - 1 is the last occurrence because upper is the first index with value greater than target.The candidate interval has length:
1high - lowEach loop iteration chooses one midpoint and discards at least roughly half of the remaining interval:
high = mid keeps the left portion;low = mid + 1 keeps the right portion.The number of iterations grows logarithmically with n:
1lowerBound: O(log n) time
2upperBound: O(log n) timeEach iteration uses a fixed number of variables:
1n, low, high, midEach helper uses:
1O(1) auxiliary spaceFinding both endpoints performs one lower-bound search and one upper-bound search:
1O(log n) + O(log n) = O(log n)The factor of two is constant. The range-reporting function also uses O(1) auxiliary space.
Incorrect assumption: If A[mid] == target, return mid.
1if A[mid] == target:
2 return midExposing input:
1A = [1, 3, 3, 3, 5]
2target = 3The first midpoint is index 2, where A[2] == 3. Returning immediately can produce:
12The required first occurrence is index 1.
Correction: For lower bound, equality follows the true branch:
1if A[mid] >= target:
2 high = midThe update continues searching left.
Incorrect assumption: The lower bound is always an occurrence.
1lower = lowerBound(A, target)
2return [lower, lower]Exposing input:
1A = [1, 3, 5]
2target = 4The lower bound is 2, because index 2 is where 4 would be inserted.
1A[2] = 5Claiming index 2 as a match is wrong.
Correction: Check both range and value before reporting an occurrence:
1if lower == length(A) or A[lower] != target:
2 return [-1, -1]high = mid - 1 with a half-open intervalIncorrect line:
1if A[mid] >= target:
2 high = mid - 1Exposing input:
1A = [1, 3]
2target = 3Start with:
1low = 0
2high = 2
3mid = 1Since A[1] >= 3, the incorrect update makes:
1high = 0The update skips insertion index 1, which is the correct lower bound.
Correction: In a half-open interval, mid remains a possible answer, so keep it:
1high = mid| Input | Lower bound | Upper bound | Occurrence result |
|---|---|---|---|
A = [], target = 3 | 0 | 0 | [-1, -1] |
A = [3, 3, 3], target = 3 | 0 | 3 | first 0, last 2 |
A = [1, 2, 4], target = 0 | 0 | 0 | absent |
A = [1, 2, 4], target = 3 | 2 | 2 | absent; index 2 is only an insertion position |
A = [1, 2, 4], target = 5 | 3 | 3 | absent |
When the lower bound equals n, do not access A[lower]. It is outside the array.
Implement this executable objective:
Implement
lowerBound(A, target)andupperBound(A, target)for a nondecreasing integer array, then return[first, last]for a target as[-1, -1]when absent; tests include empty arrays, all-equal arrays, absent interior values, and endpoint duplicates.
Your implementation will be tested against these contracts:
lowerBound returns the first index with A[i] >= target, or length(A).upperBound returns the first index with A[i] > target, or length(A).target.[-1, -1].1def lower_bound(a, target):
2 low, high = 0, len(a) # half-open [low, high)
3 while low < high:
4 mid = low + (high - low) // 2
5 if a[mid] >= target:
6 high = mid # mid may be the answer, keep it
7 else:
8 low = mid + 1
9 return low
10
11def upper_bound(a, target):
12 low, high = 0, len(a)
13 while low < high:
14 mid = low + (high - low) // 2
15 if a[mid] > target: # the only change from lower bound
16 high = mid
17 else:
18 low = mid + 1
19 return low
20
21def first_and_last(a, target):
22 lower = lower_bound(a, target)
23 if lower == len(a) or a[lower] != target:
24 return [-1, -1]
25 return [lower, upper_bound(a, target) - 1]
26
27a = [1, 3, 3, 3, 5]
28print(lower_bound(a, 3))
29print(upper_bound(a, 3))
30print(first_and_last(a, 3))1import java.util.Arrays;
2
3public class Main {
4 static int lowerBound(int[] a, int target) {
5 int low = 0, high = a.length; // half-open [low, high)
6 while (low < high) {
7 int mid = low + (high - low) / 2;
8 if (a[mid] >= target) high = mid; // mid may be the answer, keep it
9 else low = mid + 1;
10 }
11 return low;
12 }
13
14 static int upperBound(int[] a, int target) {
15 int low = 0, high = a.length;
16 while (low < high) {
17 int mid = low + (high - low) / 2;
18 if (a[mid] > target) high = mid; // the only change from lower bound
19 else low = mid + 1;
20 }
21 return low;
22 }
23
24 static int[] firstAndLast(int[] a, int target) {
25 int lower = lowerBound(a, target);
26 if (lower == a.length || a[lower] != target) return new int[]{-1, -1};
27 return new int[]{lower, upperBound(a, target) - 1};
28 }
29
30 public static void main(String[] args) {
31 int[] a = {1, 3, 3, 3, 5};
32 System.out.println(lowerBound(a, 3));
33 System.out.println(upperBound(a, 3));
34 System.out.println(Arrays.toString(firstAndLast(a, 3)));
35 }
36}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int lowerBound(const vector<int>& a, int target) {
6 int low = 0, high = (int)a.size(); // half-open [low, high)
7 while (low < high) {
8 int mid = low + (high - low) / 2;
9 if (a[mid] >= target) high = mid; // mid may be the answer, keep it
10 else low = mid + 1;
11 }
12 return low;
13}
14
15int upperBound(const vector<int>& a, int target) {
16 int low = 0, high = (int)a.size();
17 while (low < high) {
18 int mid = low + (high - low) / 2;
19 if (a[mid] > target) high = mid; // the only change from lower bound
20 else low = mid + 1;
21 }
22 return low;
23}
24
25int main() {
26 vector<int> a = {1, 3, 3, 3, 5};
27 int lower = lowerBound(a, 3);
28 cout << lower << endl;
29 cout << upperBound(a, 3) << endl;
30 if (lower == (int)a.size() || a[lower] != 3) cout << "[-1, -1]" << endl;
31 else cout << "[" << lower << ", " << upperBound(a, 3) - 1 << "]" << endl;
32}1function lowerBound(a, target) {
2 let low = 0, high = a.length; // half-open [low, high)
3 while (low < high) {
4 const mid = low + Math.floor((high - low) / 2);
5 if (a[mid] >= target) high = mid; // mid may be the answer, keep it
6 else low = mid + 1;
7 }
8 return low;
9}
10
11function upperBound(a, target) {
12 let low = 0, high = a.length;
13 while (low < high) {
14 const mid = low + Math.floor((high - low) / 2);
15 if (a[mid] > target) high = mid; // the only change from lower bound
16 else low = mid + 1;
17 }
18 return low;
19}
20
21function firstAndLast(a, target) {
22 const lower = lowerBound(a, target);
23 if (lower === a.length || a[lower] !== target) return [-1, -1];
24 return [lower, upperBound(a, target) - 1];
25}
26
27const a = [1, 3, 3, 3, 5];
28console.log(lowerBound(a, 3));
29console.log(upperBound(a, 3));
30console.log(`[${firstAndLast(a, 3).join(', ')}]`);They differ in one comparison. Lower bound moves high left when A[mid] >= target, upper bound when A[mid] > target. On [1, 3, 3, 3, 5] with target 3 they return 1 and 4.
Run lower bound, then check that lower < n and A[lower] == target. If so, the first index is lower and the last is upper bound minus 1. Otherwise return [-1, -1].
The insertion index that keeps the array nondecreasing. For [1, 2, 4] and target 3 it returns 2. Check A[lower] == target before calling it a match, and never read A[n].
Equal values can sit on both sides of mid. In [1, 3, 3, 3, 5] the first midpoint is index 2, which is not the first 3. Lower bound keeps searching left with high = mid.
In [low, high), mid is still a possible answer when the test is true. With [1, 3] and target 3, high = mid - 1 sets high to 0 and skips index 1, the correct answer.