Binary Search
Binary search eliminates half of the search space with each comparison, achieving O(log n) time on sorted data. Beyond simple element lookup, binary search can be applied to any problem where the search space is monotonic — meaning there's a clear boundary between valid and invalid answers. This generalization (binary search on answer) is a key technique for optimization problems.
When to Use
- →The input array is sorted or can be treated as sorted
- →You need to find an element or boundary in O(log n) time
- →The search space has a monotonic property (all valid answers on one side, invalid on the other)
- →You need to find the minimum or maximum value that satisfies a condition
Approach
Classic binary search maintains left and right bounds and repeatedly checks the middle element. If the target is smaller, search the left half; if larger, search the right half. The tricky part is handling boundaries correctly to avoid infinite loops and off-by-one errors.
For rotated sorted arrays, determine which half is properly sorted by comparing the middle element with the leftmost. Then check if the target falls within the sorted half. This approach works because at least one half of a rotated sorted array is always properly sorted.
Binary search on answer applies when you can frame the problem as: "What is the minimum/maximum value X such that condition(X) is true?" You binary search over possible answer values, and for each candidate, check if it's feasible. The feasibility check itself might be O(n), making the total O(n log n).
Code Template
// Standard binary search
function binarySearch(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// Binary search on answer (e.g., Koko eating bananas)
function minEatingSpeed(piles, h) {
let left = 1, right = Math.max(...piles);
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
if (hours <= h) right = mid;
else left = mid + 1;
}
return left;
}
// Search in rotated sorted array
function searchRotated(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}