Most people use binary search only on sorted arrays. But the real power is binary search on the answer space — solving problems in O(log n) that look like they need O(n) or brute force.
Binary search on a sorted array is obvious. Binary search on the answer space is a superpower. Once you see it, you'll find it in problems that look completely unrelated to searching.
1// Template that handles all edge cases
2public int binarySearch(int[] nums, int target) {
3 int left = 0, right = nums.length - 1;
4 while (left <= right) {
5 int mid = left + (right - left) / 2; // avoids overflow
6 if (nums[mid] == target) return mid;
7 else if (nums[mid] < target) left = mid + 1;
8 else right = mid - 1;
9 }
10 return -1;
11}If the problem asks 'find the minimum X such that condition(X) is true' and condition is monotonic (once true, stays true), you can binary search on X. Classic examples: Koko eating bananas, minimum ship capacity, split array largest sum.
1// Koko Eating Bananas — binary search on eating speed
2public int minEatingSpeed(int[] piles, int h) {
3 int left = 1, right = Arrays.stream(piles).max().getAsInt();
4
5 while (left < right) {
6 int mid = left + (right - left) / 2;
7 if (canFinish(piles, mid, h)) right = mid;
8 else left = mid + 1;
9 }
10 return left;
11}
12
13private boolean canFinish(int[] piles, int speed, int h) {
14 int hours = 0;
15 for (int pile : piles) hours += (pile + speed - 1) / speed; // ceiling div
16 return hours <= h;
17}Recognition pattern: 'minimum/maximum X such that Y is possible'. Verify that the feasibility function is monotonic — if speed S works, then S+1 also works. That monotonicity is what makes binary search valid.
1// Find first position where nums[mid] >= target
2private int lowerBound(int[] nums, int target) {
3 int left = 0, right = nums.length;
4 while (left < right) {
5 int mid = left + (right - left) / 2;
6 if (nums[mid] >= target) right = mid;
7 else left = mid + 1;
8 }
9 return left;
10}A rotated sorted array is still partially sorted. At any mid point, one half is always sorted. Use that to decide which half the target is in — the decision boundary is what makes it tricky.
1public int search(int[] nums, int target) {
2 int left = 0, right = nums.length - 1;
3 while (left <= right) {
4 int mid = left + (right - left) / 2;
5 if (nums[mid] == target) return mid;
6
7 // Left half is sorted
8 if (nums[left] <= nums[mid]) {
9 if (target >= nums[left] && target < nums[mid]) right = mid - 1;
10 else left = mid + 1;
11 } else { // Right half is sorted
12 if (target > nums[mid] && target <= nums[right]) left = mid + 1;
13 else right = mid - 1;
14 }
15 }
16 return -1;
17}Classic answer-space binary search. Binary search on the answer (the maximum sum of any subarray) between max(nums) and sum(nums). For each candidate, greedily count how many partitions it requires.
1public int splitArray(int[] nums, int k) {
2 int left = Arrays.stream(nums).max().getAsInt();
3 int right = Arrays.stream(nums).sum();
4
5 while (left < right) {
6 int mid = left + (right - left) / 2;
7 if (canSplit(nums, k, mid)) right = mid;
8 else left = mid + 1;
9 }
10 return left;
11}
12
13private boolean canSplit(int[] nums, int k, int maxSum) {
14 int parts = 1, curSum = 0;
15 for (int n : nums) {
16 if (curSum + n > maxSum) { parts++; curSum = 0; }
17 curSum += n;
18 }
19 return parts <= k;
20}More in DSA