Binary Search
Binary search is one of the most elegant algorithms in computer science. It operates on a sorted array by repeatedly halving the search space. You begin wi...
The Divide and Conquer Idea
Binary search is one of the most elegant algorithms in computer science. It operates on a sorted array by repeatedly halving the search space. You begin with the entire array, compute the midpoint, and compare the middle element to the target. If the middle element matches, you are done. If the target is smaller, you discard the right half. If the target is larger, you discard the left half. You repeat this process on the remaining half until either you find the target or the search space collapses to zero.
Consider the sorted array 2, 5, 8, 12, 16, 23, 38, 45, 56, 72 and the target value 23. The midpoint index is 4, holding the value 16. Since 23 is greater than 16, discard indices 0 through 4. The new search space is 23, 38, 45, 56, 72. The new midpoint holds 45. Since 23 is less than 45, discard 45, 56, 72. The remaining space is 23, 38. The midpoint is 23, which matches. The search took three comparisons instead of the six a linear search would need on average.
Time complexity is O(1) in the best case when the middle element is the target on the first try, O(log n) on average and in the worst case. Space complexity is O(1) for the iterative version and O(log n) for the recursive version due to call-stack frames.
A critical implementation detail is computing the midpoint. Writing mid = (low + high) / 2 can cause integer overflow when low and high are large. The safe form is mid = low + (high - low) / 2.
Interview tip: when asked to implement binary search, immediately write the safe midpoint formula and explain why. This small detail distinguishes candidates who have actually debugged production code from those who only know the textbook version.
Iterative vs Recursive Implementations
Binary search can be written either iteratively or recursively, and understanding the trade-offs between the two forms is important for interviews and production work. The iterative form uses a while loop with two pointers, low and high, converging toward the target. The recursive form calls itself with a narrowed range on each invocation.
Iterative pseudocode: set low to 0 and high to n-1. While low is less than or equal to high, compute mid as low plus (high minus low) divided by 2. If the array at mid equals the target, return mid. If the array at mid is less than the target, set low to mid plus 1. Otherwise set high to mid minus 1. If the loop ends, return -1.
Recursive pseudocode: if low exceeds high, return -1. Compute mid. If array at mid equals target, return mid. If array at mid is less than target, recurse with low set to mid plus 1. Otherwise recurse with high set to mid minus 1.
Both forms have the same O(log n) time complexity. The key difference is space. The iterative form uses O(1) extra space. The recursive form places a new stack frame on the call stack for each halving, consuming O(log n) space. For an array of one billion elements, log base 2 of one billion is about 30, so the recursive stack is at most 30 frames deep, which is negligible in practice. However, in environments with tight stack limits, the iterative form is safer.
A worked example: searching in a sorted array of 1,024 elements takes at most 10 comparisons with binary search compared to up to 1,024 comparisons with linear search. This demonstrates the power of the logarithmic reduction.
Interview tip: if asked which form you prefer, say iterative for production code because it avoids any risk of stack overflow and has a slightly smaller constant factor, but demonstrate that you can write both forms fluently.
Binary Search on Answer Spaces
The most powerful generalization of binary search is its application not to sorted arrays but to monotone answer spaces. Whenever you have a problem where the answer is a number in a range and you can write a predicate function that returns true for all values on one side of the answer and false for all values on the other side, binary search finds the answer in O(log(range)) evaluations of the predicate.
A classic example is finding the minimum capacity of a ship that can transport all packages within a given number of days. The capacity ranges from the heaviest single package up to the total weight of all packages. For any proposed capacity, you can simulate loading packages greedily to check whether the trip finishes in time. This simulation is the predicate. Binary search over the capacity range finds the minimum valid capacity without evaluating every possible value.
Another example is finding the square root of a number without using a math library. The answer lies between 0 and the number itself. The predicate is whether the square of the midpoint exceeds the target. Binary search on floating-point values converges to the desired precision in about 50 iterations regardless of the magnitude of the input.
Time complexity for binary search on an answer space is O(log(R) times C) where R is the size of the answer range and C is the cost of evaluating the predicate once. If the predicate runs in O(n), the total cost is O(n log R).
Space complexity remains O(1) for the iterative version.
A worked example: given an array of n integers and a budget of k operations to reduce any element by 1, what is the maximum possible minimum element? Binary search on the answer, and the predicate checks whether a given minimum is achievable within the budget by counting how many reductions are needed.
Interview tip: when you see a problem asking for the minimum or maximum of something under a constraint, immediately consider whether binary search on the answer applies. This pattern appears in a large fraction of medium and hard competitive programming problems.