Binary Search: Practice Questions

Write linear search, count the comparisons it makes, and say what it costs.

Play the number-guessing game against the computer. Guess the middle every time, and count the guesses.

How many times can you halve n before nothing is left? Build the table that answers it, and connect it to log2.

Write the canonical binary search on a sorted list. This is the version to memorise.

Print low, mid and high at every step so you can watch the range collapse.

Run binary search on an unsorted list. Show that it does not raise — it lies.

Write mid three different ways. Explain which one you would use in C or Java, and why Python does not care.

Three ways to say "not found": -1, None, and raising. Write all three and say when each is right.

Measure linear search against binary search on the same sorted data. Count probes, then time both.

State the loop invariant of binary search, then assert it on every iteration.

What changes if you write while low < high instead of while low <= high? Run both and compare.

Write the third shape: the half-open range [low, high) with high = len(values). This is the one the standard library uses.

Combine the loop condition from one shape with the update from another. Show that it hangs, with a step cap so the program still finishes.

When the target is absent, where do low and high end up? Show the pattern holds for every possible miss.

Turn the previous observation into a function: return the index where a value should be inserted to keep the list sorted.

Test binary search on the inputs that break naive implementations: empty, one item, two items, all-equal.

With duplicates in the list, which index does plain binary search return? Show that the answer is "an arbitrary one".

Find the index of the first occurrence of a value in a sorted list with duplicates.

Now find the last occurrence. Write it both ways, and note the one-character difference from Q18.

Count how many times a value appears in a sorted list, in O(log n) — without scanning.

Find the floor: the largest value in the list that is less than or equal to the target.

Find the ceiling: the smallest value greater than or equal to the target. Then note that you already wrote it.

Binary search a sorted list of strings, and then a list of dates. Show that the algorithm never mentions numbers.

Search a list of records sorted by one field. Write it with an explicit key function.

Meet bisect_left and bisect_right. Show that they are exactly the two boundary searches you have already written, and time them against yours.

Given a sorted list and a target, return the index if it is found, otherwise the index where it would be inserted.

Given a sorted list with duplicates, return the first and last index of a target as a pair, or [-1, -1].

Redo the previous question with bisect, and use it to answer four different counting questions in one line each.

Find the smallest value strictly greater than the target, and the largest value strictly less. Note how they differ from ceiling and floor.

Find the value in a sorted list closest to a target. Break ties toward the smaller value.

Find the k values closest to a target in a sorted list, returned in sorted order.

Generalise binary search: given a boolean list that is all False then all True, find the index of the first True. Then show why this generalisation is the whole topic.

You have n versions and an is_bad(v) API. Once a version is bad, every later one is bad. Find the first bad version with as few API calls as possible.

You cannot see the data at all — you can only ask "is my guess too high, too low, or correct?". Write the search against that interface.

Compute the integer square root of n — the largest x with x * x <= n — using only integer arithmetic.

Given a sorted list of distinct integers, find an index i with values[i] == i. Then show why distinctness is required.

A sorted list holds n distinct numbers drawn from 0..n. Exactly one is missing. Find it in O(log n).

Given a sorted list of distinct positive integers, find the k-th positive integer that is missing from it.

Find a peak in an unsorted list — an element greater than both its neighbours — in O(log n). Explain how binary search can work on unsorted data.

A bitonic list increases and then decreases. Find its maximum, then search it for an arbitrary value in O(log n).

A sorted list has been rotated an unknown number of places. Find its minimum in O(log n).

Find how many places a sorted list has been rotated, and use that to search it with a single ordinary binary search.

Search a rotated sorted list for a target in a single binary search pass.

Add duplicates to the rotated list. Show that the worst case becomes O(n), and write the version that is still correct.

Search an m x n matrix whose rows are sorted and where each row starts after the previous row ends. Treat it as one flat sorted list.

Now the harder matrix: rows sorted left to right and columns sorted top to bottom, but with no relationship between the end of one row and the start of the next. Find a target.

You can read values[i] but you cannot ask for the length — reading past the end returns a sentinel. Find a target in O(log p), where p is its position.

Given a list of non-overlapping intervals sorted by start, find which interval contains a query point.

Count how many values fall in [lo, hi], and extract them, in O(log n + k).

You have met six binary-search shapes. Build the decision table that tells you which one a problem needs, and implement all six behind one interface.

Here is the idea that turns binary search from a lookup into a technique. Solve a problem with no array in it: find the smallest square-shaped plot of land that fits n trees planted 3 metres apart.

Write the reusable answer-space template, and a checker that proves a feasibility function is monotone before you trust it.

Packages must ship in order within days days. Find the smallest ship capacity that makes it.

Koko eats bananas from n piles at k bananas per hour, one pile at a time. Find the smallest k that finishes within h hours.

Split a list into m contiguous parts so the largest part-sum is as small as possible. Return that minimum largest sum.

n books with page counts must be given to k students in order, each student getting a contiguous block. Minimise the maximum pages any student reads.

Place k cows in stalls at given positions so the closest pair is as far apart as possible. This is the mirror image of everything so far.

Flowers bloom on given days. You need m bouquets of k adjacent flowers each. Find the earliest day you can make them.

Find the smallest divisor such that the sum of every value divided by it (rounded up) stays under a threshold.

Find the k-th smallest value in a matrix whose rows and columns are both sorted, without flattening it.

Find the median of two sorted arrays in O(log(min(m, n))) — without merging them.

Generalise: find the k-th smallest element of two sorted arrays.

Binary search over real numbers: compute a square root to six decimal places. Then explain why low < high no longer terminates.

Compute the n-th root of a positive number with a fixed iteration count, and handle the case where the true root lies outside your first bracket.

Gas stations sit at given positions. Add k new stations anywhere to minimise the largest gap between adjacent stations. Answer to within 1e-6.

Sorting costs O(n log n) and each search then costs O(log n). Measure the crossover: at how many queries does sort-then-search beat repeated linear scanning?

Search a large list of records by a sorted field, three ways, and measure which is fastest.

Build a store where set(key, value, timestamp) records a value and get(key, timestamp) returns the value in effect at that moment.

Write the mirror template properly: find the largest value for which a condition holds. Then show the three ways people get it wrong.

Write the answer-space reference card: one function, one checklist, and five worked problems solved by filling in a single feasibility test.

Catalogue every way a binary search can fail to terminate, and build a harness that detects each one automatically.

(low + high) // 2 rounds down. Show exactly when that breaks a search, and write the rounding-up midpoint that fixes it.

Simulate 32-bit arithmetic and reproduce the binary-search overflow bug that shipped in the JDK. Then find the other places in this topic where overflow would bite outside Python.

Binary search on unsorted data does not raise. Build the defences: a debug assertion, a cheap sampled check, and a strategy for the case that is worst of all — nearly sorted data.

The list is sorted — just not the way the search compares. Four ways this happens, and how to make the mismatch impossible.

Here are four implementations of "first occurrence". Exactly one is correct. Find the bugs by differential testing rather than by reading.

bisect_left and bisect_right differ only when the target is present. Find four places where that difference is the whole answer.

Run an answer-space search against a feasibility function that is not monotone. Show that it returns a real-looking number, and build the check that catches it.

Write a float binary search that never terminates, and three that do. Explain what goes wrong at the limits of floating point.

The search is correct and the list is sorted, but the comparison itself misbehaves. None, mixed types, NaN, and a broken __lt__.

Mutate the list while a search is in progress, and let a cached key list go stale. Two bugs that only appear under concurrency or long-lived state.

Two ways to make binary search slower than a linear scan: insort in a loop, and re-sorting per query. Measure both.

Binary search assumes values[i] is free. Simulate a container where it is not, and show the algorithm becomes worse than a linear scan.

Here is a binary search that passes a thorough-looking test suite and is wrong. Find the input class the suite never covers, and write the test that would have caught it.

Five binary searches from a real code review. Find every bug, say what it costs, and fix each one.

Build a SortedIndex class: a collection that stays sorted and answers every ordered query you have met in this topic. Include the costs in the docstrings, honestly.

Build git bisect: find the commit that introduced a bug, given a list of commits and a test. Handle commits that cannot be tested.

Build prefix autocomplete over a sorted word list using two binary searches. Rank the results, and measure it against scanning.

Build a leaderboard: submit scores, then answer rank, percentile, top-k, and "players near me" queries.

Find the highest request rate a service can sustain while keeping its 99th-percentile latency under a limit. This is answer-space search against a simulation.

Build a time-series store with as-of lookups, range extraction, and bucketed downsampling — all on sorted timestamps.

Split a sorted key space across k servers so the busiest server is as lightly loaded as possible. Then verify the plan.

Build a configurable band classifier — grades, tax brackets, shipping tiers — and test the boundaries properly.

Write a planner that chooses between scanning, sorting-then-searching, and hashing — from statistics about the workload. Then check its decisions by measurement.

Build a reusable harness that fuzzes any binary search implementation, catches hangs, and shrinks a failure to its smallest reproducing input.

Explain binary search to three audiences: a twelve-year-old, a working developer who has never needed it, and an interviewer who wants the proof. Same idea, three depths.

"Our product search got slow after we added a million items, and sometimes it returns nothing for products we know exist." Work the diagnosis.

Design a lookup that answers "what is the value at time t" for a billion readings, using at most 25 probes and O(1) extra memory, where the data lives on disk and does not fit in RAM.

A full transcript. "Find a target in a rotated sorted array." Watch the parts that earn marks — and the parts that lose them.

Build an ordered analytics engine that uses every technique in this topic: boundary searches for the query surface, answer-space search for planning, and a verification suite that proves the whole thing.