Binary Search — Shrinking Search Space with Confidence
Internalise the binary search loop so you can apply it to sorted arrays, answer-range problems, and monotonic predicates.
Problem Statement
Build a robust binary search template that eliminates off-by-one mistakes and adapts to both index lookups and predicate-based searches.
Why This Problem Matters
- Binary search is the fastest way to locate thresholds in monotonic functions or sorted data—an evergreen interview favourite.
- Variations include leftmost/rightmost occurrence, search on answer space, and checking feasibility with a helper function.
- Demonstrates precision with indices, mid calculations, and loop invariants.
Thought Process
Define the invariant clearly
Decide if your interval is inclusive or half-open. Consistently maintain and communicate it.
Prevent overflow in mid calculation
Use low + Math.floor((high - low) / 2) to stay safe in languages with integer overflow.
Adapt comparisons to the target use case
For predicate searches, store the best answer seen while narrowing the range.
Step-by-Step Reasoning
- Initialise low and high bounds.
- While low <= high (inclusive interval) evaluate mid.
- Compare mid to the target or evaluate predicate.
- Discard the half that cannot contain the answer and continue.
Dry Run
Array [2, 3, 5, 9, 12], target = 9
mid = 5 → go right, mid = 9 → found. Return index 3.
Find smallest capacity that ships packages within days
Search capacity range. Predicate simulates shipping days. Binary search narrows to the minimal feasible load.
Complexity Analysis
Time
O(log n)
Space
O(1)
Why
Each iteration halves the search space. Only a handful of integers are stored as state.
Annotated Solution
public class BinarySearchTemplate {
public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}This inclusive-interval template is the baseline. To find first/last occurrence, record answers along the way and continue searching the appropriate side.
Common Pitfalls
- Forgetting to move the bounds when nums[mid] equals target during variant implementations.
- Using mid = (left + right) / 2 in languages susceptible to integer overflow.
- Failing to terminate when search spaces become empty leads to infinite loops.
Follow-Up Questions
- Implement leftmost/rightmost bias by adjusting bounds after finding the target.
- Apply binary search to the “search on answer space” pattern using feasibility predicates.
- Combine binary search with prefix sums for problems like splitting arrays or minimising maximum workloads.