These are the notes for DSA episode 12, the first episode of the binary search block (the sliding window block ended with episode 11). The problem is Find First and Last Position of Element in Sorted Array (LeetCode 34). The brute force scans the whole array for every query (O(n) each) and times out on ten lakh rows and one lakh queries. Binary search uses the one word the brute force ignores, sorted, to throw away half the array at every step: about 20 checks for ten lakh rows. You learn one template, the lower bound, and get both the first and the last position from it. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A state board publishes a result sheet: ten lakh students, sorted by marks, lowest to highest. A school principal asks: which students scored exactly 87? Because the sheet is sorted, all the 87s sit together in one block of rows. The whole answer is two numbers: the first row of the block and the last row. And principals will ask this for many different scores.
Problem statement
Given an array a sorted in non-decreasing order (equal values may repeat) and a target t, return [first index of t, last index of t], or [-1, -1] if t is not in the array. The solution must run in O(log n) time per query.
| a | t | answer |
|---|---|---|
| [5, 7, 7, 8, 8, 10] | 8 | [3, 4] |
| [5, 7, 7, 8, 8, 10] | 6 | [-1, -1] |
| [5, 7, 7, 8, 8, 10] | 5 | [0, 0] (first element) |
| [5, 7, 7, 8, 8, 10] | 10 | [5, 5] (last element) |
| [5, 7, 7, 8, 8, 10] | 11 | [-1, -1] (bigger than everything) |
| [2, 2, 2, 2, 2] | 2 | [0, 4] (all equal) |
| [] | 0 | [-1, -1] (empty array) |
Solution 1: brute force (scan everything)
Walk the whole array. The first time you see t, record first; every time you see it, update last.
import java.util.*;
public class Main {
static int[] searchRange(int[] a, int t) {
int first = -1, last = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == t) {
if (first == -1) first = i;
last = i;
}
}
return new int[]{first, last};
}
public static void main(String[] args) {
int[] a = {5, 7, 7, 8, 8, 10};
System.out.println(Arrays.toString(searchRange(a, 8)));
System.out.println(Arrays.toString(searchRange(a, 6)));
}
}
Output:
[3, 4]
[-1, -1]
Correct. Now the real result sheet: ten lakh sorted marks and one lakh queries (the answers are added up so the output stays short):
int n = 1000000, q = 100000;
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i / 3;
long t0 = System.nanoTime(), sum = 0;
for (int k = 0; k < q; k++) {
int[] r = searchRange(a, (int) (k * 7919L % 400000));
sum += r[0] + r[1];
}
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(sum + " " + ms + " ms");
Result: Time Limit Exceeded.
Why it is slow
- One query is a full scan: O(n).
- 10⁵ queries × 10⁶ rows = 10¹¹ steps, minutes of work.
- The code would work exactly the same on a shuffled array. It never uses the fact that the array is sorted.
In a sorted array, one look at the middle element tells you about a whole half: if it's too small, everything to its left is too small too.
The key insight: the dictionary trick
You never look for "mango" by reading a dictionary from page 1:
| With a dictionary | In code |
|---|---|
| Open it near the middle | mid = the middle index, look at a[mid] |
| The word comes earlier: ignore every later page | keep the left half (hi = mid) |
| The word comes later: ignore every earlier page | keep the right half (lo = mid + 1) |
| Repeat on what's left | halve until one place is left: O(log n) |
Each step halves the range, so the number of steps is about log₂ n:
| Rows left | after |
|---|---|
| 1,000,000 | 0 steps |
| about 1,000 | 10 halvings |
| 1 | 20 halvings (log₂ 10⁶ ≈ 19.9) |
One lakh queries × two searches × 20 checks ≈ 4 × 10⁶ checks instead of 10¹¹.
Solution 2: ONE template, the lower bound
Don't search for the target; search for a boundary:
lowerBound(a, t)= the first indexiwitha[i] >= t(ornif there is none).
lo = 0, hi = n // the answer is always in [lo, hi]
while lo < hi:
mid = lo + (hi - lo) / 2
if a[mid] < t: lo = mid + 1 // mid is too small: throw it and everything left of it away
else: hi = mid // mid might be the answer: keep it
return lo // lo == hi: one place left
Why it works (the invariant, a fact that stays true on every step): everything before lo is < t, and everything from hi on is >= t. Each step shrinks [lo, hi) by at least one, so the loop ends, and when lo == hi that boundary is the answer.
hi starts at n (one past the end), not n - 1, because "every element is smaller than t" is a valid answer: t would go at index n.
The lower bound is also the insert position: where t would go to keep the array sorted.
Dry run: lowerBound([5, 7, 7, 8, 8, 10], 8)
| lo | hi | mid | a[mid] | decision |
|---|---|---|---|---|
| 0 | 6 | 3 | 8 | 8 >= 8 → hi = 3 |
| 0 | 3 | 1 | 7 | 7 < 8 → lo = 2 |
| 2 | 3 | 2 | 7 | 7 < 8 → lo = 3 |
| 3 | 3 | stop: first = 3 |
lowerBound(a, 9) returns 5 (the 10), so last = 5 - 1 = 4.
First and last from one function
first = lowerBound(a, t)
if first == n or a[first] != t → [-1, -1] // t is not in the array
last = lowerBound(a, t + 1) - 1 // the first bigger element, one step back
The code, typed live
The template on its own, with main printing lowerBound(a, 8), lowerBound(a, 6) and lowerBound(a, 11):
static int lowerBound(int[] a, int t) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < t) lo = mid + 1;
else hi = mid;
}
return lo;
}
Output:
3
1
6
3 is the first 8; 6 is missing and would be inserted at index 1 (right after the 5); 11 would go at index 6, past the end.
The full solution with every edge case:
import java.util.*;
public class Main {
static int lowerBound(int[] a, int t) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < t) lo = mid + 1;
else hi = mid;
}
return lo;
}
static int[] searchRange(int[] a, int t) {
int first = lowerBound(a, t);
if (first == a.length || a[first] != t)
return new int[]{-1, -1};
int last = lowerBound(a, t + 1) - 1;
return new int[]{first, last};
}
public static void main(String[] args) {
int[] a = {5, 7, 7, 8, 8, 10};
System.out.println(Arrays.toString(searchRange(a, 8)));
System.out.println(Arrays.toString(searchRange(a, 6)));
System.out.println(Arrays.toString(searchRange(a, 5)));
System.out.println(Arrays.toString(searchRange(a, 10)));
System.out.println(Arrays.toString(searchRange(a, 11)));
int[] same = {2, 2, 2, 2, 2};
System.out.println(Arrays.toString(searchRange(same, 2)));
System.out.println(Arrays.toString(searchRange(new int[0], 0)));
}
}
Output:
[3, 4]
[-1, -1]
[0, 0]
[5, 5]
[-1, -1]
[0, 4]
[-1, -1]
The same ten lakh rows and one lakh queries that timed out before:
83338264250 37 ms
(The milliseconds vary from run to run; the sum is the same as the brute force would give.)
The same solution in C++ and Python
#include <bits/stdc++.h>
using namespace std;
int lowerBound(const vector<int>& a, int t) {
int lo = 0, hi = (int)a.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < t) lo = mid + 1;
else hi = mid;
}
return lo;
}
vector<int> searchRange(const vector<int>& a, int t) {
int first = lowerBound(a, t);
if (first == (int)a.size() || a[first] != t) return {-1, -1};
int last = lowerBound(a, t + 1) - 1;
return {first, last};
}
int main() {
vector<int> a = {5, 7, 7, 8, 8, 10};
for (int t : {8, 6, 11}) {
auto r = searchRange(a, t);
cout << "[" << r[0] << ", " << r[1] << "]\n";
}
// the standard library does the same with lower_bound / upper_bound
auto lo = lower_bound(a.begin(), a.end(), 8) - a.begin();
auto hi = upper_bound(a.begin(), a.end(), 8) - a.begin();
cout << lo << " " << hi - 1 << "\n";
}
Output:
[3, 4]
[-1, -1]
[-1, -1]
3 4
def lower_bound(a, t):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2 # Python ints never overflow
if a[mid] < t:
lo = mid + 1
else:
hi = mid
return lo
def search_range(a, t):
first = lower_bound(a, t)
if first == len(a) or a[first] != t:
return [-1, -1]
return [first, lower_bound(a, t + 1) - 1]
a = [5, 7, 7, 8, 8, 10]
print(search_range(a, 8)) # [3, 4]
print(search_range(a, 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]
import bisect # the standard library has the same thing
print(bisect.bisect_left(a, 8), bisect.bisect_right(a, 8) - 1) # 3 4
Output:
[3, 4]
[-1, -1]
[-1, -1]
3 4
C++ lower_bound / upper_bound and Python bisect_left / bisect_right are exactly this template (upper_bound = first element > t).
Three classic bugs
Bug 1: lo = mid (an infinite loop)
if (a[mid] < t) lo = mid;
On [5, 7, 7, 8, 8, 10] with t = 8: Time Limit Exceeded, on six numbers. When lo = 2, hi = 3, mid = 2, a[2] = 7 < 8, so lo = 2 again, forever. Rule: every branch must shrink the range. lo = mid + 1 throws mid away (it is known to be too small); hi = mid keeps it (it might be the answer).
Bug 2: reading a[first] without checking first == n
if (a[first] != t)
With t = 11, lowerBound returns 6 (past the end):
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6
at Main.searchRange(Main.java:15)
at Main.main(Main.java:22)
Always check first == a.length before reading a[first] (the || short-circuits, so a[first] is never read when the first part is true).
Bug 3: (lo + hi) / 2 overflows
public class Main {
public static void main(String[] args) {
int lo = 1500000000, hi = 2000000000;
System.out.println((lo + hi) / 2);
System.out.println(lo + (hi - lo) / 2);
}
}
Output:
-397483648
1750000000
lo + hi = 3.5 × 10⁹ is bigger than Integer.MAX_VALUE (2,147,483,647), so it wraps to a negative number. This bug was in the JDK's own Arrays.binarySearch for years (fixed in 2006). These values are realistic when you binary search on the answer (episode 14). lo + (hi - lo) / 2 never overflows because hi - lo fits.
Complexity
| Approach | Time per query | Extra space | 10⁶ rows, 10⁵ queries |
|---|---|---|---|
| Linear scan | O(n) | O(1) | Time Limit Exceeded |
| Lower bound, twice | O(log n) | O(1) | about 37 ms |
Binary search needs the array sorted. If it isn't, sorting costs O(n log n) once, which pays off when there are many queries.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (a[mid] < t) lo = mid; |
Time Limit Exceeded (even on 6 elements) | the range stops shrinking when hi = lo + 1 |
lo = mid + 1 |
if (a[first] != t) with t = 11 |
ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6 |
lowerBound can return n |
check first == a.length first |
int mid = (lo + hi) / 2; |
-397483648 for lo = 1.5 × 10⁹, hi = 2 × 10⁹ |
int overflow | lo + (hi - lo) / 2 |
hi = a.length - 1 with while (lo < hi) |
[5, 4] for t = 10 |
the answer n can never be returned, so lowerBound(a, 11) gives 5 |
hi = a.length (half-open range [lo, hi)) |
hi = mid - 1 in the lower bound |
[-1, -1] for t = 8 (answer is [3, 4]) |
mid might be the answer, and it was thrown away |
hi = mid |
Arrays.binarySearch for the first occurrence |
2 for [2, 2, 2, 2, 2] |
it returns any matching index | write the lower bound |
lowerBound(a, t + 1) with t = Integer.MAX_VALUE |
[0, -1] for a = {Integer.MAX_VALUE} |
t + 1 overflows to Integer.MIN_VALUE |
use an upper bound (first a[i] > t: change < to <=) |
Mini project: the result-sheet lookup
Read n sorted marks, then answer queries: for each mark m, print how many students scored exactly m (lowerBound(m + 1) - lowerBound(m)) and how many scored at least m (n - lowerBound(m)). Extend it to "how many scored between 60 and 80, inclusive?" (lowerBound(81) - lowerBound(60)). Every query is O(log n).
Practice
- Count how many times
tappears, in O(log n).
Solution
lowerBound(a, t + 1) - lowerBound(a, t). For [5, 7, 7, 8, 8, 10] and t = 8: 5 - 3 = 2 (run: prints 2).
- Search Insert Position (LeetCode 35): return the index of
t, or where it would be inserted.
Solution
That is exactly lowerBound(a, t). For [1, 3, 5, 6]: t = 5 → 2, t = 2 → 1, t = 7 → 4 (run: prints 2 1 4).
- Integer square root of
x(the largestkwithk * k <= x) with the same template.
Solution
Find the first k with k * k > x, then subtract 1. Use long so mid * mid can't overflow:
static int isqrt(int x) {
long lo = 0, hi = (long) x + 1;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (mid * mid <= x) lo = mid + 1; else hi = mid;
}
return (int) (lo - 1);
}
isqrt(8) = 2, isqrt(16) = 4, isqrt(2147483647) = 46340 (run: prints 2 4 46340).
- Why can't
Arrays.binarySearchanswer this problem?
Solution
With duplicates it returns some matching index, not the first: Arrays.binarySearch(new int[]{2, 2, 2, 2, 2}, 2) printed 2. When the key is missing it returns -(insertion point) - 1: for 6 in [5, 7, 7, 8, 8, 10] it printed -2 (insertion point 1).
Quick quiz
What does lowerBound(new int[]{1, 3, 3, 3, 9}, 4) return?
- 4
- 3
- -1
- 5
Answer
4. 4 is missing, but the lower bound never returns -1: it returns where 4 would be inserted. The first element >= 4 is 9, at index 4.
Interview questions
- What does binary search need? A sorted array, or more generally a condition that is false, false, ..., then true, true (monotonic), so one check tells you which half to drop.
- Why
hi = midbutlo = mid + 1?a[mid] >= tmeans mid might be the answer, so keep it;a[mid] < tmeans mid is definitely not, so drop it. Both shrink the range, so the loop ends. - How do you get the last occurrence?
lowerBound(t + 1) - 1, or an upper bound (first> t) minus 1. - Why
lo + (hi - lo) / 2?lo + hican overflow anint;hi - locan't. - Time and space? O(log n) time per query, O(1) space; the brute force is O(n) per query.
- What does the lower bound return when
tis missing? Its insert position, between 0 and n.
Glossary
| Term | Meaning |
|---|---|
| Sorted (non-decreasing) | Each element is >= the one before it; equal values may repeat |
| Linear scan | Checking elements one by one from the start: O(n) |
| Binary search | Repeatedly checking the middle of a sorted range and discarding the half that can't hold the answer: O(log n) |
| log₂ n | How many times you can halve n before reaching 1; log₂ of 10⁶ is about 20 |
lo, hi, mid |
The ends of the range still being searched, and its middle index |
Half-open range [lo, hi) |
Includes lo, excludes hi; here hi starts at n, one past the end |
| Invariant | A fact that stays true on every loop step: everything before lo is < t, everything from hi on is >= t |
| Lower bound | The first index with a[i] >= t, or n if none; also the insert position |
| Upper bound | The first index with a[i] > t |
| Insert position | Where t would go to keep the array sorted |
| Infinite loop | A loop whose condition never becomes false (here: the range stops shrinking) |
| Integer overflow | A result bigger than the type's maximum (2,147,483,647 for int), which wraps to a wrong value |
| Monotonic condition | A yes/no test that switches from false to true only once along the array |
ArrayIndexOutOfBoundsException |
Java's runtime error for reading an index outside 0..length-1 |
Summary
- A linear scan per query is O(n) and ignores that the array is sorted: 10¹¹ steps, Time Limit Exceeded.
- Sorted data lets one look discard half: about 20 checks for ten lakh rows.
- One template, the lower bound:
lo = 0, hi = n;a[mid] < t → lo = mid + 1, elsehi = mid; returnlo. first = lowerBound(t), checkfirst == n || a[first] != t,last = lowerBound(t + 1) - 1.- Always
mid = lo + (hi - lo) / 2, and make every branch shrink the range.
Next episode: Search in a rotated sorted array.