Chapter 15 of 30
Binary Search (Array & Answer Space)
Master binary search on sorted arrays, STL binary search functions, and binary search on the answer space.
Binary Search on a Sorted ArraySTL Binary Search FunctionsBinary Search on the AnswerBoundary Handling
Share:
Binary Search (Array & Answer Space)
Binary search is the fundamental algorithm for searching in sorted data. But its real power comes from binary search on the answer — when you can verify a candidate answer in O(n), you can find the optimal answer in O(n log MAX).
Binary Search on a Sorted Array
Classic Implementation
hljs cpp
// Find index of target in sorted array, or -1 if not found
int binarySearch(vector<int> &a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
Why lo + (hi - lo) / 2?
mid = (lo + hi) / 2 can overflow when lo + hi > INT_MAX. The safe version avoids this.
STL Binary Search Functions
hljs cpp
vector<int> v = {1, 3, 5, 7, 9, 9, 9};
// binary_search: does element exist?
bool exists = binary_search(v.begin(), v.end(), 5); // true
// lower_bound: first element >= x
auto lb = lower_bound(v.begin(), v.end(), 5);
// points to 5 (index 2)
// upper_bound: first element > x
auto ub = upper_bound(v.begin(), v.end(), 5);
// points to 7 (index 3)
// Count of elements == x
int count = ub - lb; // 1
// Count of elements < x
int less = lower_bound(v.begin(), v.end(), x) - v.begin();
// Count of elements <= x
int lessEqual = upper_bound(v.begin(), v.end(), x) - v.begin();
Using with Custom Comparators
hljs cpp
// Find first element where comparator returns true
auto it = lower_bound(v.begin(), v.end(), value, [](int elem, int val) {
return elem < val;
});
Binary Search on the Answer
Many problems ask: "What is the minimum/maximum X such that condition P(X) is true?"
Pattern
hljs cpp
// Find minimum X where P(X) is true
int lo = MIN_ANSWER, hi = MAX_ANSWER;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
hi = mid; // mid works, try smaller
} else {
lo = mid + 1; // mid doesn't work, need larger
}
}
// lo is the minimum valid answer
// Find maximum X where P(X) is true
int lo = MIN_ANSWER, hi = MAX_ANSWER;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (check(mid)) {
lo = mid; // mid works, try larger
} else {
hi = mid - 1; // mid doesn't work, need smaller
}
}
// lo is the maximum valid answer
Example: Minimum Speed to Arrive On Time
hljs cpp
bool canArrive(int speed) {
double time = 0;
for (int i = 0; i < n - 1; i++) {
time += ceil((double)dist[i] / speed);
}
time += (double)dist[n - 1] / speed;
return time <= hour;
}
int lo = 1, hi = 1e7;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canArrive(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
Example: Split Array Largest Sum
hljs cpp
bool canSplit(int maxSum) {
int count = 1, current = 0;
for (int x : a) {
if (current + x > maxSum) {
count++;
current = x;
} else {
current += x;
}
}
return count <= m;
}
int lo = *max_element(a.begin(), a.end());
int hi = accumulate(a.begin(), a.end(), 0);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canSplit(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
Boundary Handling
Finding First Occurrence
hljs cpp
int lo = 0, hi = n - 1, result = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) {
result = mid;
hi = mid - 1; // keep searching left
} else if (a[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
Finding Last Occurrence
hljs cpp
int lo = 0, hi = n - 1, result = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) {
result = mid;
lo = mid + 1; // keep searching right
} else if (a[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
Summary
- Binary search: O(log n) on sorted data
- STL:
lower_bound(first >= x),upper_bound(first > x),binary_search(exists?) - Binary search on the answer: verify in O(n), search in O(log MAX)
- Always use
lo + (hi - lo) / 2to avoid overflow - The loop invariant is key: define what
loandhimean, and ensure they converge
Prefer reading offline? Download the full book as a PDF.
Download Free Book