Get your boarding pass

Binary search interview questions

Binary search is easy to describe and famously easy to get wrong. The interview skill is a template you can write without off-by-one errors, and the insight that you can search on an answer, not only on an array.

How do I solve binary search interview questions?

Binary search finds a target, or the first position that satisfies a condition, by halving the search range each step, which takes logarithmic time. It needs a monotonic condition: false for a stretch, then true. It applies to sorted arrays, rotated arrays and to searching for the smallest feasible answer.

Practise binary search

How to recognise a binary search problem

The data is sorted, or sorted in two parts as in a rotated array.

The question asks for the minimum or maximum value that makes something possible (the smallest speed, the least capacity, the largest size) and checking one candidate is easy.

A linear scan is too slow and the answer has the false-then-true shape.

How to build the solution

Define the range of possible answers, low and high, and the condition that is false below the answer and true from it.

Loop while low < high. Compute mid as low + (high - low) / 2 to avoid overflow. If the condition holds at mid, the answer is mid or lower, so set high = mid; otherwise set low = mid + 1.

When the loop ends, low is the first position where the condition holds. Check whether it exists at all.

For searching on an answer, write the feasibility check as a separate function and reason about its cost: total time is log of the range times the check.

Classic problems to practise

Binary Search, Search Insert Position, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Capacity to Ship Packages, Median of Two Sorted Arrays, Time Based Key-Value Store.

Mistakes interviewers see

Infinite loops from mixing the two styles: if you set low = mid you must round mid up, and the standard low = mid + 1 version pairs with high = mid.

Overflow when computing (low + high) / 2 with large 32-bit values.

Not stating the invariant, then adjusting bounds by trial and error. Say what is true of everything left of low and right of high.

Forgetting that duplicates change what first and last occurrence mean, and not handling an empty range or a target outside it.

Practise it as an interview

Take a topic-based interview on binary search to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.

Frequently asked questions

What is the time complexity of binary search?

Logarithmic in the size of the range, because each step halves it. Searching on an answer multiplies that by the cost of one feasibility check.

Can I use binary search on unsorted data?

Only if the question has a monotonic condition you can test, as in searching for the smallest feasible answer. Plain unsorted data has no such order.

Keep reading