Binary search looks simple, yet it is one of the most commonly failed topics in technical interviews. Candidates know the idea of halving a sorted array, but stumble on boundaries, infinite loops, and variants where the “array” is not obvious. This guide covers the four binary search patterns that appear most often in coding interviews in 2026, with a reusable template for each.
Why Binary Search Trips Up Strong Candidates
The algorithm runs in O(log n), but the implementation is full of off-by-one traps. Interviewers use it as a signal for careful reasoning: can you define an invariant and stick to it? Most bugs come from mixing inclusive and exclusive bounds, or from computing the midpoint carelessly. Under time pressure, even experienced engineers rewrite the loop three times before it terminates correctly.
Pick one template and stick to it
Choose a single convention, such as a half-open interval [lo, hi), and use it for every problem. Switching conventions mid-solution is the number one cause of infinite loops.
int lo = 0, hi = n; // search in [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow
if (condition(mid)) hi = mid;
else lo = mid + 1;
}
return lo; // first index where condition is trueThe invariant is simple: the answer, if it exists, is always inside [lo, hi). Every branch must shrink that interval, which guarantees termination.
Pattern 1: Classic Exact Match
Find a target in a sorted array. Compare nums[mid] to the target and discard half. This is the warm-up, but practice it until you can write it without hesitation, including returning -1 for a missing target. Interviewers often start here and then add a twist, so a fluent baseline buys you time for the harder follow-up.
Pattern 2: Lower Bound and Upper Bound
Find the first or last position of a value, or the insertion point. This is the half-open template above with condition(mid) defined as nums[mid] >= target. Problems such as “Find First and Last Position of Element in Sorted Array” and “Search Insert Position” reduce to this single idea.
- Lower bound: the first index with nums[i] >= target.
- Upper bound: the first index with nums[i] > target; the last occurrence is that index minus one.
Once you see everything as “find the first index where a condition becomes true”, duplicates stop being scary.
Pattern 3: Binary Search on the Answer
This is where interviews get interesting. Instead of searching an array, you search a range of possible answers and test feasibility with a helper function. The key requirement is monotonicity: if a value works, every larger (or smaller) value also works.
Typical problems
- Koko Eating Bananas: the minimum eating speed that finishes within h hours.
- Capacity to Ship Packages Within D Days.
- Split Array Largest Sum.
- Minimum time to complete trips or allocate books.
The recipe: set lo to the smallest plausible answer, hi to the largest, write feasible(x), then find the first x for which it returns true. State the monotonic property out loud; interviewers listen for it. Total cost is O(log(range) x cost of feasible), so mention both factors when you analyze complexity.
Pattern 4: Rotated and Partially Sorted Arrays
In “Search in Rotated Sorted Array”, one half of the range is always sorted. Identify which half, check whether the target lies inside it, and discard the other. With duplicates you may need to shrink the bounds by one when nums[lo] == nums[mid] == nums[hi], which degrades the worst case to O(n); mention this trade-off proactively. The same reasoning solves “Find Minimum in Rotated Sorted Array” and “Find Peak Element”, where you compare mid with a neighbor to decide which direction goes uphill.
Common Mistakes to Avoid
- Overflow: use lo + (hi – lo) / 2 rather than (lo + hi) / 2, especially in Java and C++.
- Infinite loops: when using hi = mid, the loop condition must be lo < hi and the other update must be mid + 1.
- Wrong return value: after the loop, check that lo is in range and actually satisfies the condition.
- Skipping edge cases: test an empty array, a single element, all-equal values, and targets outside the range.
- Non-monotonic conditions: if feasibility does not flip exactly once, binary search is the wrong tool.
How to Communicate It in the Interview
Narrate your invariant: “The answer is always in [lo, hi). If condition(mid) is true, the answer is at mid or earlier, so hi = mid.” Then dry-run a tiny example with two or three elements before declaring done. State complexity clearly: O(log n) iterations, multiplied by the cost of the feasibility check for answer-space problems. Clear narration often matters as much as the code, because it shows the interviewer how you debug your own thinking.
A Two-Week Practice Plan
- Days 1-3: exact match, search insert position, first and last position.
- Days 4-7: rotated array variants, peak element, find minimum in rotated array.
- Days 8-11: binary search on the answer (Koko, ship packages, split array).
- Days 12-14: mixed timed practice, 25 minutes per problem, explaining aloud as if an interviewer were present.
After each problem, write the invariant and the monotonic condition in one sentence. This habit turns memorized solutions into transferable skill.
Start Practicing Today
Binary search rewards repetition: after a dozen problems with one consistent template, the off-by-one anxiety fades. Pick three problems from the lists above, solve them today, and write the invariant in a comment each time. For more interview preparation resources, visit Niraswa AI.
