Binary search is like playing “guess the number” optimally. Instead of guessing randomly, you always guess the middle. With each guess, you eliminate half the possibilities. This is why binary search is O(log n)—even with a billion elements, you need at most 30 guesses.
The answer is a number in a range. Check if each candidate answer is valid. The validity forms a monotonic sequence (all NO, then all YES, or vice versa).
The Insight: Binary search works whenever you have a monotonic predicate—a condition that’s false for all values up to some point, then true for all values after (or vice versa).
int binarySearch(vector<int>& arr, int target) { int lo = 0, hi = arr.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // Avoid overflow if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { lo = mid + 1; } else { hi = mid - 1; } } return -1; // Not found}
int lowerBound(vector<int>& arr, int target) { int lo = 0, hi = arr.size(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] < target) { lo = mid + 1; } else { hi = mid; // Don't exclude mid, it might be the answer } } return lo; // First position where arr[i] >= target}
int upperBound(vector<int>& arr, int target) { int lo = 0, hi = arr.size(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] <= target) { lo = mid + 1; } else { hi = mid; } } return lo; // First position where arr[i] > target}
This is the game-changer pattern. Many problems that seem impossible become easy with this technique.
Copy
// General templatebool canAchieve(int x) { // Return true if 'x' is achievable/valid // This function must be monotonic!}int binarySearchOnAnswer() { int lo = MIN_POSSIBLE_ANSWER; int hi = MAX_POSSIBLE_ANSWER; int answer = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (canAchieve(mid)) { answer = mid; // mid is valid hi = mid - 1; // Try to find smaller valid (for minimum) // lo = mid + 1; // Try to find larger valid (for maximum) } else { lo = mid + 1; // Need larger value // hi = mid - 1; // Need smaller value (for maximum) } } return answer;}
Problem Type: “Minimize the maximum” or “Maximize the minimum”Example: Split array into K subarrays to minimize the maximum subarray sum.Approach: Binary search on the answer (the maximum sum). For each candidate, check if we can split into ≤ K subarrays.
Copy
bool canSplit(vector<int>& arr, int maxSum, int k) { int count = 1; int currentSum = 0; for (int x : arr) { if (x > maxSum) return false; // Single element too large if (currentSum + x > maxSum) { count++; currentSum = x; } else { currentSum += x; } } return count <= k;}int splitArray(vector<int>& nums, int k) { int lo = *max_element(nums.begin(), nums.end()); int hi = accumulate(nums.begin(), nums.end(), 0); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (canSplit(nums, mid, k)) { hi = mid; // Try smaller maximum } else { lo = mid + 1; } } return lo;}
Problem: Find the Kth smallest element in sorted matrix / merged sorted arrays.Approach: Binary search on the value. Count how many elements are ≤ mid.
Copy
int kthSmallest(vector<vector<int>>& matrix, int k) { int n = matrix.size(); int lo = matrix[0][0]; int hi = matrix[n-1][n-1]; while (lo < hi) { int mid = lo + (hi - lo) / 2; // Count elements <= mid int count = 0; int col = n - 1; for (int row = 0; row < n; row++) { while (col >= 0 && matrix[row][col] > mid) { col--; } count += col + 1; } if (count < k) { lo = mid + 1; } else { hi = mid; } } return lo;}
Need to find something in sorted array?├── Exact element → Standard binary search (lo <= hi)├── First >= target → Lower bound├── First > target → Upper bound└── Last <= target → Upper bound - 1Need to optimize (min/max) something?├── Can you define canAchieve(x)?│ ├── Is it monotonic? → Binary search on answer│ └── Not monotonic → Different technique└── No clear predicate → Not binary search
