Most binary search interview questions never mention a sorted array. The hard ones hide the search: you get a bus schedule, a string with removable characters, or an integer x you have to reduce to zero, and it is on you to notice that some quantity is monotonic and can be searched in O(log n). The skill interviewers actually test is not writing the loop (you can memorize that), it is recognizing when a problem is secretly a binary search. This guide covers the three patterns that account for nearly every binary search question we see, the templates for each, and the off-by-one and overflow bugs that quietly fail candidates who otherwise had the right idea.
The one idea that unlocks the pattern
Binary search works on any search space with a monotonic predicate. That is the whole trick. If you can define a boolean function feasible(x) that returns false, false, ..., false, true, true, ..., true as x increases (or the reverse), you can binary search for the boundary in O(log range). The array does not have to be sorted. The array may not even be the thing you search.
Ask yourself two questions when you are stuck:
- Is there a value where "too small" flips to "just right and beyond"? That flip point is your answer.
- Can I check a single candidate value in linear (or better) time?
If both are yes, you are looking at a binary search, even when the prompt looks like greedy, DP, or two pointers. This is why binary search shows up across so many company question sets, from Google to Amazon: it is a reasoning test disguised as an algorithm.
Pattern 1: Search an index in a (nearly) sorted structure
This is the version everyone learns first, and interviewers still ask it, but with a twist that breaks the naive template. The classic twist is rotation.
Search in Rotated Sorted Array II is the canonical trap. The array is sorted then rotated at an unknown pivot, and, critically, values are not distinct. At each step you compare nums[mid] against nums[lo] to decide which half is sorted, then check whether the target falls inside that sorted half. The duplicates break the standard rotated-array logic: when nums[lo] == nums[mid] == nums[hi] you cannot tell which side is sorted, so you shrink both ends by one. That single edge case turns the worst case from O(log n) into O(n), and naming that tradeoff out loud is often what the interviewer is waiting to hear.
The template for index search we recommend:
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoid overflow
if nums[mid] == target:
return mid
# decide which half is sorted, then narrow
...
return -1
Use the lo <= hi with mid +/- 1 form when you are hunting an exact index. Reserve the lo < hi form for the boundary-search patterns below. Mixing the two conventions in one solution is the fastest way to introduce an off-by-one under time pressure.
Pattern 2: Binary search on the answer
This is the pattern that separates mid-level from senior performance, and it is where "binary search question" almost never appears in the prompt. Instead of searching an array, you search the space of possible answers.
The recipe:
- Identify the answer's numeric range,
[low, high]. - Write
feasible(candidate)that returns whethercandidatesatisfies the constraint. - Binary search for the smallest (or largest)
candidatewherefeasibleflips.
Minimum Time to Complete Trips is the cleanest example in our bank. You are given an array time of per-bus trip durations and a target number of trips. Binary search on the total time t: given t, the number of trips is sum(t // time[i]), which is monotonically non-decreasing in t. Find the smallest t where the trip count reaches the target. The array itself is never sorted; you sort nothing. The search space is time, bounded above by min(time) * totalTrips.
The Latest Time to Catch a Bus rewards the same instinct. You want the latest time you can arrive and still board, which is a maximization over a monotonic feasibility check. Many candidates reach for sorting plus simulation and miss that the arrival time is the thing to binary search.
Maximum Number of Removable Characters is our favorite "why is this binary search" problem. You are given strings s and p (a subsequence of s) and an array removable of indices. You want the largest k such that after removing the first k indices in removable, p is still a subsequence of s. Feasibility is monotonic: if p survives after removing k characters, it survives after removing fewer. So binary search k, and for each candidate run a linear subsequence check. That turns a scary-looking string problem into O(n log n) with a five-line predicate.
If you have never drilled this pattern, it feels like a different technique from Pattern 1. It is the same loop; only the search space changed. If you find yourself reaching for a linear scan to find a threshold value, pause and check whether the threshold is monotonic first. We wrote about a related instinct in our guide to the two pointers technique, and the two patterns often compete for the same problem.
Pattern 3: Binary search as a subroutine
Here binary search is not the whole solution; it is a fast lookup inside a larger algorithm, usually DP or a greedy scan. Spotting it means noticing a repeated "find the position of x in a sorted thing" step and replacing a linear scan with bisect.
Maximum Number of Events That Can Be Attended II (a staff-level problem) is DP plus binary search. You sort events by end day, then for each event binary search for the next event whose start day is after the current event's end. The DP decides attend-or-skip while binary search supplies the transition index in O(log n) instead of O(n), which is the difference between passing and TLE at scale.
Count Subarrays With Score Less Than K and Minimum Operations to Reduce X to Zero both live at the boundary between prefix sums, sliding window, and binary search. For the score problem, prefix sums are monotonic for a positive array, so you can binary search the right endpoint for each left endpoint, though a sliding window is often cleaner. Knowing both approaches lets you pick the one you can implement bug-free in the room. 132 Pattern is a reminder that not every "Binary Search" tag means you should binary search: the optimal solution uses a monotonic stack, and binary search over an ordered set is a slower but acceptable fallback. Part of interview judgment is recognizing when the tag is a red herring.
The bugs that quietly cost offers
Getting the idea right and the loop wrong is the most common way we watch candidates lose a binary search problem in mock interviews. Three failure modes dominate:
Integer overflow in the midpoint. Writing mid = (lo + hi) / 2 can overflow when lo + hi exceeds the integer max. Josh Bloch documented this in a well-known 2006 Google Research post arguing that nearly all binary searches and mergesorts shipped with this latent bug for years; the fix is mid = lo + (hi - lo) // 2. In Python the overflow will not bite you, but interviewers at C++ and Java shops still expect the safe form, and writing it signals maturity.
Boundary and loop-condition mismatch. Decide up front: are you searching for an exact index (while lo <= hi, move past mid) or for a boundary (while lo < hi, keep mid as a candidate)? Pick one convention per problem and never update lo and hi asymmetrically without a reason.
Wrong feasibility direction. In answer-space problems, confirm whether you want the first true or the last true. Getting the predicate backwards produces an answer that is off by exactly one and passes small tests but fails the hidden ones.
Our advice: write the invariant as a comment before you write the loop. State what lo and hi mean and which side is always feasible. Two lines of prose prevent most of these bugs.
How to practice this pattern
Do not grind fifty variants of "find element in sorted array." Instead, take five problems that do not look like binary search (start with Minimum Time to Complete Trips and Maximum Number of Removable Characters) and force yourself to articulate the monotonic predicate out loud before coding. Then practice explaining the boundary invariant to an interviewer, because stating the invariant is graded as highly as the code at senior and staff levels. Reproducing that pressure is exactly what our AI mock interviews are built for, and it is where most candidates find the gap between "I can solve it" and "I can explain it while someone watches."
FAQ
How do I know a problem is binary search if it does not mention a sorted array?
Look for a monotonic relationship: some value where feasibility flips from false to true (or the reverse) and can be checked in linear time. Words like "minimum time," "maximum number," or "largest k such that" are strong signals. If sorting the input is not required but a threshold clearly exists, suspect binary search on the answer.
Should I use the lo <= hi or lo < hi template?
Use lo <= hi with mid +/- 1 moves when searching for an exact index that may not exist. Use lo < hi while keeping mid as a live candidate when searching for a boundary or the smallest/largest value satisfying a predicate. Pick one convention per problem and keep it consistent.
Is binary search still commonly asked in 2026?
Yes. It remains a staple because it doubles as a reasoning test, not just a syntax check. The trend we see is fewer plain sorted-array questions and more answer-space and DP-with-binary-search variants at the mid and senior levels.
What is the most common bug interviewers watch for?
Off-by-one errors from an inconsistent loop condition, and the classic midpoint overflow (lo + hi) / 2 in Java or C++. Writing lo + (hi - lo) / 2 and stating your loop invariant preempts both.
How many binary search problems should I do before an interview?
Quality over volume. Ten well-chosen problems spanning all three patterns (index, answer space, subroutine) with clean explanations beats fifty rote sorted-array drills. Prioritize the ones where the search space is not the input array.