Notes › DSA
Binary Search
Binary search finds a target in a sorted array by looking at the middle and throwing away the half that can't contain it. Each step halves the search space, so it takes O(log n) time — about 30 steps for a billion elements.
The basic version
int binarySearch(vector<int>& a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow of (lo + hi)
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1; // target is on the right
else hi = mid - 1; // target is on the left
}
return -1; // not found
}
Iterative: O(log n) time, O(1) space. A recursive version uses O(log n) stack.
Why lo + (hi - lo) / 2?
(lo + hi) can overflow when both are near 2³¹. In Python it doesn't matter, but use the safe form in C++/Java.
Lower bound and upper bound (the most useful template)
- lower_bound(x): first index with
a[i] >= x - upper_bound(x): first index with
a[i] > x
int lowerBound(vector<int>& a, int x) {
int lo = 0, hi = a.size(); // answer is in [lo, hi]; hi = size means "none"
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) hi = mid; // mid might be the answer — keep it
else lo = mid + 1;
}
return lo;
}
Built-ins: C++ lower_bound(a.begin(), a.end(), x), Python bisect_left(a, x) / bisect_right, Java Collections.binarySearch (returns any match).
Uses:
- Count of x =
upper_bound(x) − lower_bound(x). - First occurrence =
lower_bound(x)(check it equals x). - Last occurrence =
upper_bound(x) − 1. - Insert position =
lower_bound(x).
Search in a rotated sorted array
[4,5,6,7,0,1,2] — one half around mid is always sorted.
def search(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t: return mid
if a[lo] <= a[mid]: # left half is sorted
if a[lo] <= t < a[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half is sorted
if a[mid] < t <= a[hi]: lo = mid + 1
else: hi = mid - 1
return -1
Find a peak element
A peak is bigger than its neighbours. If a[mid] < a[mid+1], a peak exists on the right; otherwise on the left (including mid). O(log n) even though the array isn't sorted.
Binary search on the answer
When the question is "find the minimum x such that condition(x) is true" and the condition is monotonic (false, false, …, true, true), binary search over x.
Example — Koko eating bananas: piles [3,6,7,11], 8 hours. What's the minimum eating speed?
def can_finish(piles, h, speed):
return sum((p + speed - 1) // speed for p in piles) <= h # ceil division
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if can_finish(piles, h, mid): hi = mid # works — try slower
else: lo = mid + 1 # too slow
return lo
Answer: 4. Complexity: O(n log max).
Same pattern: ship packages within D days, allocate books (minimise the maximum pages), aggressive cows (maximise the minimum distance — search for the largest x where the condition holds), square root of n.
Square root without sqrt()
Find the largest x with x·x ≤ n: binary search on x in [0, n] (use long for x·x).
Binary search on 2-D matrices
If each row is sorted and the first element of a row is greater than the last of the previous one, treat it as one sorted array of size r·c: index k → (k / c, k % c).
How to avoid infinite loops
| Loop | Update rules | Ends with |
|---|---|---|
while (lo <= hi) |
lo = mid + 1, hi = mid - 1 |
lo > hi |
while (lo < hi), mid rounds down |
hi = mid and lo = mid + 1 |
lo == hi |
while (lo < hi), need lo = mid |
use mid = lo + (hi - lo + 1) / 2 (round up) |
lo == hi |
Test your code on arrays of size 0, 1 and 2 — that's where the bugs hide.
Complexity summary
| Problem | Time |
|---|---|
| search / lower bound | O(log n) |
| rotated array, peak | O(log n) |
| binary search on answer | O(log(range) × cost of the check) |
Practice
Binary Search problems. Classic list: Binary Search, First and Last Position, Search Insert Position, Rotated Sorted Array, Find Minimum in Rotated Array, Peak Element, Koko Eating Bananas, Capacity to Ship Packages, Median of Two Sorted Arrays.
Interview one-liners
- Needs sorted data or a monotonic condition.
- Each step halves the search space → O(log n).
- Use
lo + (hi − lo) / 2to avoid overflow. - "Minimise the maximum" / "maximise the minimum" → binary search on the answer.
- Related: Time & Space Complexity (Big-O), DSA Patterns.