Sequences and Queries

What is this?

These are the trickiest, most satisfying uses of binary search — the ones where you're not searching for a value you can see at all. You might be hunting the kth missing number, the dividing line between two sorted lists, or who was winning an election at some moment in time. The shared move is to invent a quantity that only ever grows as you move along, then binary-search the exact point where it crosses the target. A common companion trick is to do one slow pass up front to build a lookup, so that afterwards a flood of questions each get answered almost instantly.

💡 Fun fact: The "do the heavy work once, then answer each question fast" idea here is the same one behind database indexes — building the index is slow, but afterward millions of lookups fly, which is why a search that crawls without one can run thousands of times slower.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Binary search can locate things that are not values at all — a count of missing numbers, a partition point, the right moment in a timeline. The trick is to define a quantity that increases monotonically with the index (or the candidate), then binary-search the place where that quantity crosses your target. These are the hardest, most rewarding applications of the technique.

The pattern

Each problem here builds a monotonic signal and searches it. For "missing element" questions, the number of values missing before index i only grows as i grows, so you binary-search for where the missing-count reaches your target. The same gap-counting idea answers "the kth missing positive" by treating absent numbers as a running deficit.

A second idea is partition search: rather than merging two sorted arrays, binary-search the cut that splits the combined elements into a correct left and right half — that is how the median falls out in log time without ever merging.

A third idea is precompute, then query: do one linear pass to build a structure (a leader-over-time timeline, prefix counts of an item), then answer each query with a binary search or an array lookup. The work moves from per-query to one-time setup.

The problems

Missing Element in Sorted Array — find the kth missing value. Count missing before index: at index i, missing-so-far is nums[i] − nums[0] − i; binary-search the first index where that count reaches k, then offset into the gap.

Kth Missing Positive Number — find the kth absent positive integer. Same gap counting: at index i, the missing count is nums[i] − (i + 1); binary-search where it first reaches k.

Median of Two Sorted Arrays — the classic O(log(min(m, n))) problem. Partition search: binary-search a cut in the smaller array that, paired with the complementary cut in the larger, puts the right counts on each side and satisfies the order condition — the median sits at the boundary.

Online Election — answer "who led at time t?" repeatedly. Precompute leaders in one pass over the votes, store the time of each lead change, then bisect time to find the leader for each query in O(log n).

Plates Between Candles — count plates strictly between two candles for many queries. Build prefix counts of plates and, for each query, find the nearest candle inward on each side (precomputed or via binary search), then subtract prefix counts.

Key takeaways

• Search a monotonic quantity, not the raw array. Missing-counts, partitions, and lead-times all grow predictably — binary-search the crossing point.
• Gap counting answers "missing" questions. A simple formula at each index turns absence into a searchable count.
• Partition instead of merge. The median comes from finding the right split, never from combining the arrays.
• Precompute once, query many. Build a timeline or prefix array up front so each query is O(log n) or O(1).
• Why this chapter matters: it stretches binary search to its limits, the level expected for hard interview rounds and the foundation for query-heavy problems.