In this article
Before you start
This page is one pattern in the coding interview patterns and method learning path. If you can read a loop and a list index, you can follow it.
Why interviewers ask this
A binary search is short enough to write on a whiteboard and easy enough to get quietly wrong, so it shows whether a candidate reasons about boundaries or guesses at them. Candidates report being asked to write one by hand, to order two teams of players by height for a photograph, to explain efficient sorting in Python, and to solve "binary search on the answer" problems such as the banana-eating puzzle and a maximize-the-minimum-distance room problem. These are reports from candidates, not a public company list.
A weak answer writes the loop from memory and fixes it by trial and error. A strong answer states what stays true on every pass, names the stopping condition, tests an empty array and a missing target, and says when sorting first is worth its cost. This page builds exactly that, one rung at a time.
The sorting and binary search ladder from first principles
- Binary search
- Binary search is a method that finds a value in a sorted array by comparing the target with the middle item and discarding the half that cannot contain it, repeating until the range is empty, so the work grows with the logarithm of the size rather than the size itself.
- Search on the answer
- Search on the answer is a pattern that applies binary search to a range of possible answers instead of array positions, using a yes-or-no test that is false for small guesses and true for large ones, or the reverse, and flips only once.
In plain words
Think of a dictionary. You never read from page one. You open the middle. You see whether your word comes before or after. Then you throw away half the book. That only works because the words are in order. The analogy breaks in one place. A dictionary has fixed pages. A program can search a range of numbers with no pages, such as "how many hours". In code, lo and hi are the first and last page you have not yet ruled out, and each look at the middle moves one of them.
In one precise sentence: sort so that order exists, discard half the candidates per step, find the first or last match, then do it again on guessed answers.
Step 1: Sort first so that order does the work
Sorting is the first rung because every later rung needs order. Python gives two tools: undefined modifies the list in place and undefined builds a new sorted list. Both accept a key function that is called once on each element, as the same documentation page shows. A sort key is the value that decides where an element goes in the order.
The photograph question shows the idea. Sort each team by height, then compare players pairwise. With illustrative heights in centimeters, team A sorts to 168, 172, 176, 181, 190 and team B to 170, 175, 180, 185, 195; every player of A is shorter than the player of B in the same position, so A can stand in front.1 Input: two unordered lists. Output: two ordered lists and one check. Sorting costs about n log n comparisons, a figure explained in the worked example. You now have order; the next step spends it.
Step 2: Binary search halves a sorted range
Binary search finds a target in a sorted array by keeping two indexes, lo and hi, that bound every place the target could still be. Each pass reads the middle item. If it equals the target, stop. If it is smaller, the target can only be to the right, so lo moves past the middle. If it is larger, hi moves before it. The search ends when lo passes hi. Python's undefined module likewise works on lists that are already sorted.
def binary_search(a, target):
lo, hi = 0, len(a) - 1 # target, if present, is in a[lo..hi]
while lo <= hi:
mid = lo + (hi - lo) // 2 # not (lo + hi) // 2: see below
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1 # range is empty: not presentThe comment on mid is the common error. In a language with 32-bit signed integers, the largest value is 2,147,483,647. With lo at 1,500,000,000 and hi at 2,000,000,000, the sum is 3,500,000,000, wraps to a negative number (in Java; in C and C++ it is undefined behavior), and the "middle" becomes −397,483,648. The form lo + (hi - lo) // 2 gives 1,750,000,000.1 Joshua Bloch's post is titled "Nearly All Binary Searches and Mergesorts are Broken" for this kind of reason; the safe form costs nothing, so write it in every language.
Step 3: An insertion point finds the first or last equal item
An insertion point answers "where would this value go?" rather than "is it here?". Python's bisect module is called bisect because it uses a basic bisection algorithm, and bisect_left returns the position before any existing equal entries, while bisect_right returns a position that comes after any existing entries. The Python 3 module is for keeping a list in sorted order without sorting it again after each insertion.
For the array 1, 2, 2, 2, 3 and the target 2, the left point is 1 and the right point is 4, so the target occurs 3 times.1 For a missing target the two points agree, so a membership test is: take the left point, then check that it is inside the array and that the item there equals the target. In the ten-item array of the worked example, the target 20 has insertion point 5.1 bisect finds a position, never proof of presence, which is why the extra check exists.
Step 4: Search on the answer halves guessed values
Search on the answer replaces array positions with a range of candidate answers and replaces "compare with the middle item" with a test of feasibility. The banana-eating problem asks for the smallest eating speed that finishes all piles within a time limit. Any speed that works means every faster speed works too, so the test flips once, which is what makes halving legal.
Take illustrative piles of 3, 6, 7 and 11 bananas and 8 hours. The search range is 1 to 11. Guess 6: the hours needed are 6, so 6 works and the answer is at most 6. Guess 3: 10 hours, too slow, so the answer is at least 4. Guess 5: 8 hours, works. Guess 4: 8 hours, works. The range closes on 4 after four tests, instead of up to 11 tests in the worst case.1 The same shape solves "place 3 people in rooms at positions 1, 2, 4, 8 and 9 to maximize the smallest gap": the best gap is 3.1
Step-by-step description
- Sorting creates the order that later rungs use.
- Binary search discards half of a sorted range per pass.
- An insertion point finds the first or last equal item.
- The same halving works on guessed answers.
- Sorting is the first rung.
- Binary search halves a sorted range.
- An insertion point finds the first or last equal item.
- Search on the answer halves guessed values.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Trace the search for 23 in the sorted array 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 (illustrative). Pass 1: lo 0, hi 9, mid 4, value 16, too small, so lo becomes 5. Pass 2: lo 5, hi 9, mid 7, value 56, too large, so hi becomes 6. Pass 3: lo 5, hi 6, mid 5, value 23, found at index 5 after 3 probes.1
The cost follows from halving. The worst case is the number of times a range can be halved, plus one. Arrays of 16, 1,000 and 1,000,000 items need at most 5, 10 and 20 probes, against up to 1,000 or 1,000,000 for a scan.1
| Quantity | Value (computed) |
|---|---|
| Worst-case probes, 16 items | 5 |
| Worst-case probes, 1,000 items | 10 |
| Worst-case probes, 1,000,000 items | 20 |
| Orderings of 5 distinct items | 120 |
| Lower bound on worst-case comparisons, 5 items | at least 7 |
| Lower bound on worst-case comparisons, 1,000 items | at least 8,530 |
| Banana puzzle: tests needed on a range of 11 speeds | 4 |
The sorting rows come from a counting argument. Five distinct items can arrive in 120 orders, and each comparison at best halves the orders still possible, so at least 7 comparisons are needed, since 2 to the power 7 is the first power of two that reaches 120. For 1,000 items the same count gives a lower bound of 8,530.1 A bound says no method can do better; it does not say the bound is reached for every n. That is why comparison sorting is described as n log n.
Text description of the diagram
- Binary search needs at most 5 probes for 16 items.
- Binary search needs at most 10 probes for 1,000 items and 20 for 1,000,000 items.
Trade-offs and edge cases
Sorting is not free. For one lookup in an unsorted list, a scan of n items beats sorting at about n log n and then searching, so sort first only when you search many times or the sorted order answers the question itself, as in merge intervals and k closest points to the origin.
Duplicates change what "found" means, so state whether you want any match, the first or the last, and use the matching edge variant from Step 3. An empty array must return cleanly: with hi at minus one the loop never starts. Search on the answer fails when the test does not flip once; a test that is true, false, true across the range has no safe half to discard. Answers that are real numbers need a fixed number of passes or a tolerance, since the range never becomes empty.
Sometimes order is the wrong tool. A hash map answers "is it here?" without sorting, as in subarray sum equals k, and a window that moves only forward, as in longest substring without repeating characters, needs neither.
Text description of the diagram
- Sorting needs only keys that can be compared.
- Searching needs a sorted array.
- Searching the answer needs a yes-or-no test that flips once.
Sorting needs only keys that can be compared. Searching needs a sorted array. Searching the answer needs a yes-or-no test that flips once. The test in Step 4 must be monotonic: once it turns true for a guess, it stays true for every larger guess, which is the same one-way property a sorted array has.
How to answer it in an interview
Write a binary search and tell me when you would use it.
First I confirm, or ask, that the array is sorted, because binary search needs order. I keep lo and hi so the target is always inside them, take the middle as lo plus half the gap so it cannot overflow, and discard the half that cannot hold the target. I stop when lo passes hi. With duplicates I return the left edge. If a problem asks for a smallest or largest value, I look for a yes-or-no test that flips once and search that range. I test an empty array, one item and a missing target.
The spoken structure: say the precondition, say what stays true each pass, write the loop, name the overflow-safe midpoint, then test the edges.
Common mistakes
- "I'll binary search the array as it comes." (wrong) The input may be unsorted. (right) "First I confirm, or ask, that it is sorted, or I sort it, because binary search needs order."
- "I wrote
(lo + hi) // 2." (wrong) In fixed-width integer languages the sum can wrap. (right) "I uselo + (hi - lo) // 2." - "The
bisectresult is the index of my target." (wrong) It is an insertion point, which also exists for missing values. (right) "I check the index is in range and the item equals the target." - "I'll use
hi = midandlo = midin the same loop." (wrong) The range may stop shrinking and loop forever. (right) "I move one bound pastmid, or use the left-edge form withlo < hi."
Follow-up questions
How to implement efficient sorting in Python?
Call sorted(data, key=...) for a new list or data.sort(key=...) to reorder the list in place, and let the key function compute the value to compare. Write your own sort only if the interviewer asks for the algorithm itself; see Python interview questions for related language questions.
How do you write a binary search on a whiteboard?
State the invariant first, write the loop from Step 2, and walk the trace of the worked example on a tiny array. Finish with the three edge tests.
How would you order two teams so shorter players are in front?
Ask what "in front" means, then sort each team by height and compare players position by position; if every front-row player is shorter than the player behind, the arrangement works.
Why does binary search need sorted input?
Discarding half the range is only safe when order tells you which half cannot contain the target. On unsorted data the discarded half might hold it.
What changes when the array has duplicates?
Plain binary search may land on any equal item. Use the left or right edge variant from Step 3 to get the first or last one, and subtract the two edges to count them.
What if the number of guesses changes?
If the answer range is ten times larger, the search needs only a few more tests, since each doubling of the range adds one test. The cost of one feasibility check, not the halving, usually dominates.
- Sort first only when order will be used more than once or answers the question itself.
- Binary search keeps a range that must contain the target and halves it each pass.
- Write the midpoint as lo plus half the gap, in every language.
- An insertion point gives the first or last equal item; always verify presence.
- Search on the answer works when a yes-or-no test flips exactly once.
Sources
- bisect: Array bisection algorithm (Python 3 documentation) — Python Software Foundation, 26 Oct 2026
- Sorting Techniques (Python 3 HOWTO) — Python Software Foundation, 26 Oct 2026
- bisect: Array bisection algorithm (Python 2.7 documentation) — Python Software Foundation (final 2.7 release, 2.7.18), 20 Apr 2020
- Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken — Google Research blog (Joshua Bloch), 2 Jun 2006
