Binary Search Problems

Six classic interview problems — Binary Search, Search a 2D Matrix, Koko Eating Bananas, Find Minimum in Rotated Sorted Array, Search in Rotated Sorted Array and Median of Two Sorted Arrays — solved from zero with one idea: throw away half of the candidates at every step, but only the half that provably cannot hold the answer. For each problem you will see the slow obvious idea, the reason each half can be dropped, the pseudocode, the Dart code, and an animation you can feed your own input, with lo, mid and hi drawn on the data and the dropped part grayed out. By the end you will own one loop template, know when to write lo < hi and when lo ≤ hi, and be able to binary search an answer instead of a list.

Halving the candidates: the template, bounds and searching the answer

A long hotel corridor with 1000 rooms, numbered in order, and you want room 637. You do not knock on every door. You walk to the middle door, read 500, and know at once that rooms 1 to 500 are all wrong — the whole left part of the corridor is gone in one look. You walk to the middle of what is left, read 750, and now 750 to 1000 are gone too. Every look throws away half of the doors that are still possible. After about ten looks only one door is left.

You met binary search for the first time in C01 · Your first two algorithms: linear and binary search. This lesson turns it into a tool you can bend to many problems. A few words first:

The candidates are the positions (or values) that could still be the answer. Binary search keeps them as one unbroken range from lo (low end) to hi (high end).
Sorted means every item is at least as big as the one before it. Sorting is what makes one look enough to rule out a whole side.
An invariant is a promise the loop keeps after every round, such as "if the target is anywhere, it is between lo and hi". The loop is correct because the promise is never broken and the range shrinks every round.
O(log n) ("order log n") means the work grows like the number of times you can halve n before reaching 1. For n = 10⁹ that is only 30 rounds. Big-O notation itself is explained in C03 · Growth of Functions.

The one template to remember

Every binary search in this lesson has the same four parts:

Bounds. Choose lo and hi so the answer is surely inside. For "find an index" that is 0 and n − 1 (or n, if "past the end" is a possible answer). For "find a value" it is the smallest and largest value that could ever be correct.
Loop condition. Keep going while there is more than one candidate (lo < hi) or while there is at least one (lo ≤ hi). The table below shows which one goes with which style.
The middle. mid = lo + (hi - lo) ~/ 2. In Dart ~/ is whole-number division: it drops the fraction, so the middle of 3..4 is 3, never 3.5.
Which half to keep. Look at mid and ask: can mid itself still be the answer? If it can, keep it (hi = mid). If it cannot, step past it (lo = mid + 1 or hi = mid − 1). Each move must keep the invariant true.

Style	Candidates	Loop	Moves	Ends with	Use it for
Closed range	`lo..hi`, both included; start `0`, `n − 1`	`while (lo <= hi)`	`lo = mid + 1` or `hi = mid - 1` (mid is checked and then dropped)	`lo > hi`: nothing left → "not found"	"is the target here, and where?" (Binary Search, 2D Matrix, rotated search, median)
Shrink to one	`lo..hi`, the answer is surely one of them	`while (lo < hi)`	`lo = mid + 1` or `hi = mid` (mid may be the answer, so it stays)	`lo == hi`: the answer	"the first position / smallest value where something becomes true" (bounds, Koko, rotated minimum)

The invariant, in words. Closed range: "the target, if it exists, has an index between lo and hi". Shrink to one: "the answer is between lo and hi, and it always exists". Every move in the code is chosen so that the sentence stays true. When the loop stops, the sentence tells you what you have.

An overflow-free middle

The obvious middle, (lo + hi) ~/ 2, first adds the two numbers. Dart's int on the Dart VM (phones, servers, the command line) is a 64-bit number, and adding two numbers close to the top of that range wraps around to a large negative number — an overflow. lo + (hi - lo) ~/ 2 only ever adds half of the distance to lo, so it never leaves the range. With list indexes you will not reach 2⁶² in practice, but when you binary search over values (speeds, capacities, timestamps) the bounds can be huge, and in languages with 32-bit ints this bug is famous. Compiled to JavaScript for the web, Dart ints are JavaScript numbers that stay exact only up to 2⁵³ — another reason to keep sums small. Write the safe form every time and you never have to think about it.

Lower bound and upper bound

Two questions come up again and again on a sorted list that may contain repeats:

Lower bound of x: the first index whose value is ≥ x. If x is in the list, this is its first copy. If not, it is the spot where x would be inserted to keep the list sorted.
Upper bound of x: the first index whose value is > x. It is one step past the last copy of x.

Both can be n ("past the end") when no value qualifies, so hi starts at n, not n − 1. The number of copies of x is simply upperBound − lowerBound. The two functions differ in a single character: < versus <=.

Binary search on the answer

Sometimes there is no sorted list at all — but there is a yes/no test that flips only once. "Can Koko finish the bananas eating 5 per hour?" No. 6? No. 7? Yes. 8? Yes — and every faster speed is also yes. Written out, the answers look like this:

1 ✗2 ✗3 ✗4 ✗5 ✗6 ✗7 ✓8 ✓9 ✓10 ✓

A test like this is called monotonic: as the value grows, the answer goes from "no" to "yes" and never back. That row of ✗ and ✓ is a sorted list (false before true), so binary search finds the first ✓ in O(log range) tests instead of trying every value. The recipe: (1) name the value you are searching for; (2) write ok(value); (3) convince yourself it flips only once; (4) pick lo where the answer cannot be smaller and hi where ok is surely true; (5) run the "shrink to one" template.

Koko Eating Bananas below is exactly this. So are shipping parcels within D days, splitting a list into k parts, the integer square root and many more in the question bank.

The off-by-one checklist

Almost every binary search bug is one of these. Run through them before you say "done":

Bounds include the answer. Can the answer be n (past the end)? Then hi = n. Can it be 0? Then lo = 0.
Loop condition matches the moves. hi = mid goes with while (lo < hi); with lo ≤ hi it can loop forever when lo == hi == mid.
The range shrinks every round. Because mid rounds down, mid can equal lo. So lo = mid may not move — if you need lo = mid, round the middle up: lo + (hi - lo + 1) ~/ 2 (question p05-q6 shows the endless loop).
The comparison is the right one. < or ≤ decides whether you land on the first copy, after the last copy, or anywhere.
Return the right thing. lo, lo − 1, the value a[lo], or −1 — and check it is in range before you read a[lo].
Test the tiny cases. An empty list, one item, two items, a target smaller than everything and larger than everything.

Binary search needs one look that rules out a whole side. A sorted list gives that; so does a monotonic yes/no test, a rotated list (one half is always sorted), or a matrix read row by row. Find that look, choose bounds that surely contain the answer, and decide for mid: keep it or step past it.

Binary search on unsorted data does not fail loudly — it returns a wrong answer. If the input is not sorted and you cannot find a monotonic test, sort first (O(n log n), worth it for many queries) or use a hash set (Step 13.1 · Arrays & Hashing).

Why about 30 rounds for a billion? Each round keeps at most half of the candidates (rounded up). After k rounds at most n / 2^k remain, and the loop stops when that reaches 1, so k ≈ log₂ n. 2³⁰ ≈ 1.07·10⁹, so 10⁹ items need at most 30 rounds, and doubling n adds just one more. Logarithms are explained from zero in M01 · Logs, powers, summations.

Binary Search (find the target or −1)

The task. You get a list nums sorted in increasing order with all values different, and a number target. Return the index where target sits, or −1 if it is not in the list. Your method must take O(log n) time.

Example 1

Input: nums = [-3, 0, 4, 9, 15, 22], target = 9

Output: 3

Why: nums[3] is 9.

Example 2

Input: nums = [2, 5, 8, 13], target = 6

Output: -1

Why: 6 would sit between 5 and 8, but it is not there.

Example 3

Input: nums = [7], target = 7

Output: 0

Why: one item, and it is the target.

Constraints

0 ≤ n ≤ 10⁶
−10⁹ ≤ nums[i], target ≤ 10⁹, all nums different, sorted
up to 10⁵ searches on the same list

Speed you need: a scan is O(n) per search, 10¹¹ steps for all of them → O(log n) per search (at most 20 rounds), O(1) extra space.

The "higher or lower" game with a friend thinking of a page in a 1000-page book. You say "500". They say "higher". You never say 300 again — the whole first half is out. You say "750". "Lower." Now only 501 to 749 is possible. Each answer cuts what is left in half, and you always guess the middle of what is left.

Brute force. Walk from the left and compare every item with the target. It works even on unsorted lists, but it costs O(n): a million comparisons for a million items.

Key insight. Compare the target with the middle candidate. If they are equal, done. If nums[mid] < target, then every item left of mid is even smaller (the list is sorted), so the whole left part and mid itself are out: lo = mid + 1. Otherwise the right part and mid are out: hi = mid − 1.

Why it is correct. Invariant: if the target is in the list, its index is between lo and hi. It is true at the start (the whole list). Each move drops only items that are surely too small or too big, so it stays true. The range loses at least one item per round (mid is always dropped), so the loop ends. When lo > hi the range is empty, and the invariant says the target is nowhere — return −1. This is the "closed range" style: while (lo <= hi), because a range with exactly one item (lo == hi) still has to be checked.

An edge case: the target is smaller than every item. Every look sends hi to the left, until hi falls below lo and nothing is left.

Complexity. Time O(log n) — each round halves the range, so at most ⌊log₂ n⌋ + 1 rounds (20 for a million items). Space O(1) — three whole numbers, whatever the size of the list.

Input size → what is feasible: one search on n = 10⁶ is fine either way; 10⁵ searches need binary search (2·10⁶ steps instead of 10¹¹).

Common mistakes. (1) while (lo < hi) with hi = mid - 1: the last remaining candidate is never checked, so a list like [7] returns −1. (2) hi = nums.length with this closed-range loop: nums[mid] can read one past the end and throw a RangeError. (3) lo = mid instead of mid + 1: when two candidates are left, mid == lo and the loop never ends. (4) Forgetting that Dart's List.indexOf is a linear scan, not a binary search.

Follow-ups interviewers ask. The list has repeats — return the first and last index (p05-q1) or count the copies (p05-q7). Return where the target would go (p05-q2). The list is so long you do not know its length: double an index 1, 2, 4, 8, … until you pass the target, then binary search that last stretch. Write it recursively — then the call stack uses O(log n) space.

The idea underneath: binary search from C01 · Linear and binary search, and why log n grows so slowly in C03 · Growth of Functions.

Search a 2D Matrix

The task. You get a grid of whole numbers with rows rows and cols columns (a matrix). Each row is sorted from left to right, and the first number of every row is bigger than the last number of the row above it. Return true if target is somewhere in the grid, otherwise false, in O(log(rows · cols)) time.

Example 1

Input: matrix = [[2, 4, 7, 9], [12, 15, 18, 21], [25, 30, 34, 40]], target = 18

Output: true

Why: 18 is in row 1, column 2.

Example 2

Input: the same matrix, target = 22

Output: false

Why: 22 would come between 21 and 25, but it is not there.

Example 3

Input: matrix = [[1, 3]], target = 3

Output: true

Why: a single row is just a sorted list.

Constraints

1 ≤ rows, cols ≤ 1000
−10⁹ ≤ matrix[r][c], target ≤ 10⁹
up to 10⁴ searches

Speed you need: checking every cell is 10⁶ per search, 10¹⁰ in total → O(log(rows · cols)) per search (about 20 rounds), O(1) extra space.

A book whose pages are the rows. The words run in order across each page, and the next page continues where the last one stopped. If you tore the pages out and glued them end to end, you would get one long sorted strip. You do not have to glue anything: if you know the strip position, you can work out the page (position ÷ words per page) and the place on the page (the remainder).

Brute force. Look at every cell: O(rows · cols). It ignores both kinds of order.

Key insight. Reading the matrix row by row gives one sorted list of length rows · cols. Run ordinary binary search on positions 0 .. rows · cols − 1, and turn a position p into a cell only when you need to read it: row = p ~/ cols, column = p % cols. For example, in a matrix with 4 columns, position 6 is row 6 ~/ 4 = 1, column 6 % 4 = 2.

Why it is correct. Because the first item of each row is bigger than the last item of the row above, the row-by-row reading really is sorted, so everything proven for Binary Search holds. Dividing by cols counts how many full rows come before position p, and the remainder is how far into the next row it is.

An edge case: the target is larger than everything. Every look sends lo to the right until it runs past the last cell.

Complexity. Time O(log(rows · cols)) = O(log rows + log cols). Space O(1) — no list is ever built; the division happens only for the cells we read.

Input size → what is feasible: a 1000 × 1000 grid has 10⁶ cells — one scan is fine, but 10⁴ searches need the 20-round binary search.

Common mistakes. (1) Dividing by rows instead of cols: the row is "how many full rows of cols items fit before p". Only square matrices hide this bug. (2) Using / in Dart: it returns a double, which cannot index a list — use ~/. (3) Applying this to a matrix where only rows and columns are sorted but rows overlap (like [[1, 4], [2, 5]]): the row-by-row reading is not sorted there. That kind needs the staircase walk from a corner (p05-q23).

Follow-ups interviewers ask. Rows and columns are sorted but rows may overlap: start at the bottom-left corner and step up or right — O(rows + cols) — to search or to count values ≤ x (p05-q23); then binary search on the value to find the k-th smallest (p05-q22). Each row sorted on its own and nothing else: the median of all values (p05-q26). Two binary searches instead of one (first the row, then inside it) — the same O(log) total.

The idea underneath: the same binary search, plus whole-number division and remainder from D03 · Numbers & Bits.

Koko Eating Bananas

The task. Koko has n piles of bananas; pile i holds piles[i] bananas. She picks one eating speed k (bananas per hour). Every hour she chooses one pile and eats k bananas from it; if the pile has fewer than k left, she finishes it and waits for the rest of that hour (she never moves to another pile within the same hour). She must finish everything within h hours. Return the smallest whole speed k that is fast enough.

Example 1

Input: piles = [5, 13, 21, 26], h = 7

Output: 13

Why: at 13 per hour the piles take 1 + 1 + 2 + 2 = 6 hours. At 12 per hour they take 1 + 2 + 2 + 3 = 8 hours, too many.

Example 2

Input: piles = [9, 3, 7], h = 3

Output: 9

Why: three piles in three hours means one hour per pile, so the biggest pile decides.

Example 3

Input: piles = [10], h = 4

Output: 3

Why: at 3 per hour: 3 + 3 + 3 + 1 → 4 hours. At 2 per hour it would take 5.

Constraints

1 ≤ n ≤ 10⁴
n ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Speed you need: trying every speed is up to 10⁹ speeds × 10⁴ piles → binary search on the speed, O(n log(max pile)) ≈ 3·10⁵ steps, O(1) extra space; the hour total (up to 10¹³) fits in Dart's 64-bit int.

Tuning a fan's speed dial so the room cools down in time for guests. Turn it too low and the room is still hot when they arrive; any higher setting always cools it in time. You want the quietest setting that still works. You do not try every notch from 1 upwards: you try the middle notch, and whether it works tells you which half of the dial to keep.

Brute force. Try speed 1, 2, 3, … and stop at the first speed whose total hours is ≤ h. Each try costs O(n), and the answer can be as large as the biggest pile: O(n · max(piles)).

Key insight. We are not searching a list — we are searching the answer. Name the test: ok(k) = "eating at speed k finishes within h hours". Faster never takes longer, so ok flips only once, from false to true: it is monotonic. The answer is between 1 (the slowest possible) and max(piles) (that speed finishes any pile in one hour, so n ≤ h hours always works). Binary search for the first speed where ok is true.

Ceiling division. A pile of p bananas at speed k takes p ÷ k hours rounded up — the ceiling, written ⌈p / k⌉. A pile of 7 at speed 3 takes 3 hours (3 + 3 + 1), not 2. In Dart, (p + k - 1) ~/ k rounds up using whole numbers only: adding k − 1 pushes any leftover over the next multiple of k, while an exact multiple stays where it is ((6 + 2) ~/ 3 = 2, (7 + 2) ~/ 3 = 3). It avoids (p / k).ceil(), which goes through a double.

An edge case: as many hours as piles. Only one hour per pile is allowed, so the search climbs all the way to the biggest pile.

Complexity. Time O(n log M) where M = max(piles): about log₂ M rounds (30 for 10⁹), each computing the hours for all n piles. Space O(1).

Input size → what is feasible: piles up to 100 bananas → the brute force (100 × n) is fine; piles up to 10⁹ → only the binary search on the speed finishes in time.

Common mistakes. (1) Plain p ~/ k for the hours: it rounds down, so 7 bananas at speed 3 counts as 2 hours and the answer comes out too small. (2) lo = 0: mid can become 0 and the hour formula divides by zero (Dart throws IntegerDivisionByZeroException). (3) hi = h or hi = sum(piles): still correct but wasteful; max(piles) is the tightest speed that surely works. (4) Using while (lo <= hi) with hi = mid: when lo == hi the loop never ends — the "shrink to one" template uses lo < hi.

Follow-ups interviewers ask. The same shape with a different test: the smallest ship capacity that delivers parcels in order within D days (p05-q15), the smallest possible largest part when a list is cut into k pieces (p05-q21), the first day enough neighbouring flowers have opened (p05-q16), the widest spacing for routers (p05-q25 — here you want the largest value that works, so round mid up). Real-valued answers (an average, a time in hours): loop a fixed number of times instead of comparing whole numbers (p05-q31).

The idea underneath: binary search on a monotonic test (the opening section), and whole-number division from D03 · Numbers & Bits.

Find Minimum in Rotated Sorted Array

The task. A list of different numbers was sorted in increasing order and then rotated: it was cut at some index and the front part was moved to the end. For example [3, 7, 11, 15, 18, 22] cut at index 3 becomes [15, 18, 22, 3, 7, 11]. The cut may also be at index 0 (nothing moves). Return the smallest number, in O(log n) time.

Example 1

Input: nums = [15, 18, 22, 3, 7, 11]

Output: 3

Why: the values climb to 22, drop to 3, then climb again. The minimum sits right after the drop.

Example 2

Input: nums = [6, 9, 14, 20]

Output: 6

Why: rotated by 0 — still fully sorted, so the first item is the smallest.

Example 3

Input: nums = [8, 2]

Output: 2

Why: two items; the drop is between them.

Constraints

1 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹, all different
nums is a sorted list rotated at some index 0..n − 1

Speed you need: a scan is O(n); the task asks for O(log n) time, O(1) extra space.

A clock face read starting from some random hour: 9, 10, 11, 12, 1, 2, … The numbers keep rising until one place where they drop (12 → 1), and the smallest number is right after that drop. To find the drop quickly, compare a number in the middle with the last number you can see: if the middle one is bigger than the last one, the drop must still be ahead of you.

Brute force. Look at every item and keep the smallest: O(n).

Key insight. Compare nums[mid] with nums[hi], the last candidate:

nums[mid] > nums[hi]: going from mid to hi the values end up lower, so the drop (and the minimum after it) is somewhere to the right of mid. mid itself is bigger than something, so it is not the minimum: lo = mid + 1.
nums[mid] < nums[hi]: the stretch mid..hi is sorted, so nothing right of mid is smaller than nums[mid]. The minimum is mid or to its left: hi = mid (mid stays — it may be the answer).

Why compare with hi and not with lo? If nums[mid] > nums[lo], the left part is sorted — but that is also true for a list that was not rotated at all, where the minimum is at lo, and for a rotated one, where it is to the right. Comparing with lo cannot tell these apart; comparing with hi always can. Invariant: the minimum's index is in lo..hi. Since the answer always exists, use "shrink to one": while (lo < hi), and return nums[lo].

An edge case: rotated by 0, so the list is fully sorted. Every comparison finds nums[mid] < nums[hi], and hi walks left to index 0.

Complexity. Time O(log n) — the range halves every round. Space O(1).

Input size → what is feasible: n = 10⁵ → 17 rounds instead of 10⁵ comparisons; with many queries on one list, find the minimum once — its index is also the rotation amount.

Common mistakes. (1) Comparing with nums[lo]: breaks on a list rotated by 0. (2) hi = mid - 1 in the else branch: mid may be the minimum itself, and it is thrown away. (3) while (lo <= hi) with hi = mid: when lo == hi nothing changes and the loop never ends. (4) Repeated values: when nums[mid] == nums[hi] you cannot tell the side. Then drop just hi (hi--), which makes the worst case O(n) (p05-q14).

Follow-ups interviewers ask. With repeats (p05-q14). How many times was the list rotated? It equals the index of the minimum. Find the maximum: it sits just before the minimum (index of the minimum − 1, wrapping around). Use the minimum's index to split the list into two sorted halves, then binary search the right one — another way to solve the next problem.

The idea underneath: the "shrink to one" template from the opening section; the rotated list is a sorted list cut in two, as in the sorted-array ideas of C01 · Linear and binary search.

Search in Rotated Sorted Array

The task. nums is a sorted list of different numbers that was rotated at an unknown index (as in the previous problem). Given target, return its index, or −1 if it is not there. Your method must take O(log n) time.

Example 1

Input: nums = [13, 17, 21, 2, 6, 9], target = 6

Output: 4

Why: nums[4] is 6.

Example 2

Input: nums = [13, 17, 21, 2, 6, 9], target = 10

Output: -1

Why: 10 is not in the list.

Example 3

Input: nums = [5], target = 2

Output: -1

Why: the only item is not the target.

Constraints

1 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i], target ≤ 10⁹, all nums different
nums is a sorted list rotated at some index 0..n − 1

Speed you need: a scan is O(n); the task asks for O(log n) time, O(1) extra space.

A deck of numbered cards, sorted, then cut once — the top part is put under the bottom part. Split the pile anywhere in the middle and look at the two halves: at least one of them is still in perfect order, because the single cut can only be in one of them. For the ordered half, a glance at its first and last card tells you whether your card can be inside it. If yes, search there; if not, it must be in the other half.

Brute force. nums.indexOf(target) — a scan, O(n).

Key insight. Cut the range lo..hi at mid. The drop is in at most one of the two halves, so one half is sorted, and we can tell which with one comparison:

nums[lo] ≤ nums[mid] → the left half lo..mid is sorted (no drop inside it). The target is in it exactly when nums[lo] ≤ target < nums[mid]. If so, hi = mid − 1; otherwise lo = mid + 1.
Otherwise the right half mid..hi is sorted. The target is in it exactly when nums[mid] < target ≤ nums[hi]. If so, lo = mid + 1; otherwise hi = mid − 1.

Why it is correct. For a sorted half, "is the target between its two ends?" is a complete answer: a sorted stretch holds exactly the values between its first and last item. If the target is not in the sorted half, the only place it can be is the other half — sorted or not, we keep only that one and repeat. Invariant (closed range): if the target exists, its index is in lo..hi. We use ≤ in nums[lo] ≤ nums[mid] because when lo == mid the "left half" is the single item mid, which counts as sorted.

An edge case: rotated by n − 1, so only the largest item moved to the front, and the target is exactly that item.

Complexity. Time O(log n) — one look per round, half of the range dropped each time. Space O(1).

Input size → what is feasible: n = 10⁵ → at most 17 rounds per search; with repeats allowed the worst case becomes O(n) (p05-q20).

Common mistakes. (1) nums[lo] < nums[mid] instead of ≤: with two items left (lo == mid) the code wrongly treats the right half as sorted and can miss the target. (2) Wrong strictness at the ends: the left test is nums[lo] ≤ target < nums[mid] (mid was already checked), the right test is nums[mid] < target ≤ nums[hi]. (3) Trying to find the rotation point first and then forgetting the rotation by 0. (4) Repeats like [2, 2, 2, 0, 2]: nums[lo] == nums[mid] == nums[hi] hides which half is sorted — shrink both ends by one (p05-q20).

Follow-ups interviewers ask. With repeats, return true or false (p05-q20). Two-step version: find the minimum's index (previous problem), then run plain binary search on the half that can contain the target. Count how many values are ≤ x in a rotated list: two lower-bound searches, one per sorted half.

The idea underneath: the closed-range template from the opening section, plus the minimum-finding idea of Find Minimum in Rotated Sorted Array.

Median of Two Sorted Arrays

The task. You get two sorted lists a (length m) and b (length n); at least one of them is not empty. Return the median of all m + n numbers together: the middle number when there is an odd count, or the average of the two middle numbers when the count is even. Your method must take O(log(m + n)) time — the best methods take O(log min(m, n)).

Example 1

Input: a = [1, 4, 9], b = [2, 3, 7, 10]

Output: 4.0

Why: together: 1, 2, 3, 4, 7, 9, 10 — seven numbers, the 4th is the middle one.

Example 2

Input: a = [3, 8], b = [1, 5, 6, 12]

Output: 5.5

Why: together: 1, 3, 5, 6, 8, 12 — six numbers, so the average of 5 and 6.

Example 3

Input: a = [], b = [2, 6]

Output: 4.0

Why: only b counts: (2 + 6) / 2.

Constraints

0 ≤ m, n ≤ 10⁶, 1 ≤ m + n
−10⁶ ≤ a[i], b[j] ≤ 10⁶, both sorted
up to 10⁴ different pairs of lists

Speed you need: merging is O(m + n) = 2·10⁶ per pair, 2·10¹⁰ in total → O(log min(m, n)) per pair (about 20 rounds), O(1) extra space.

Two queues of students, each already lined up by height, and the teacher wants to split everybody into a "shorter half" and a "taller half". She does not merge the queues. She says: "take the first 3 from queue A and the first 2 from queue B into the shorter half". The split is right if the tallest student she took is no taller than the shortest student she left — and she only has to compare the students standing right at the two cut points. If the cut in A took someone too tall, she moves A's cut to the left (and B's to the right, so the half keeps its size), and tries again.

Brute force. Put both lists together, sort, and read the middle: O((m + n) log(m + n)). Merging the two sorted lists (like the merge step of merge sort) gets that down to O(m + n), but it still touches every item.

The partition picture

Think of the median as a cut through all the numbers: a left half and a right half where

the left half has half = (m + n + 1) ~/ 2 numbers (for an odd total it holds the extra one, the median itself), and
every number on the left is ≤ every number on the right.

Then the median is the biggest number on the left (odd total), or the average of the biggest on the left and the smallest on the right (even total). We never build the halves. Because both lists are sorted, the left half is just a front part of a plus a front part of b: the first i items of a and the first j items of b, with i + j = half. Pick i, and j = half − i is forced.

Four numbers stand at the two cuts: aLeft = a[i − 1] and aRight = a[i] on either side of a's cut, bLeft = b[j − 1] and bRight = b[j] on either side of b's cut. Inside each list the order is already right (aLeft ≤ aRight, bLeft ≤ bRight). So condition 2 needs only the two cross checks:

aLeft ≤ bRight — the biggest taken from a is not bigger than the smallest left in b, and
bLeft ≤ aRight — the biggest taken from b is not bigger than the smallest left in a.

When a cut is at the very start or end of a list, the missing neighbour is treated as −∞ (left of the start) or +∞ (right of the end), so the check involving it always passes.

Key insight — binary search on i. If aLeft > bRight, we took too many from a: every bigger i is even worse, so search smaller i (hi = i − 1). If bLeft > aRight, we took too few from a: search bigger i (lo = i + 1). Otherwise the cut is correct. Moving i one way can only fix one of the two checks and worsen the other, so the "too many / too few" answer flips once as i grows — binary search applies. And we search over the shorter list: i ranges over 0..m and then j = half − i is always a real cut of b (between 0 and n). Searching the longer list could make j negative (p05-q32).

An edge case: one list is empty. Then a (after the swap, the empty one) has only one possible cut, i = 0, and the whole left half comes from b.

Complexity. Time O(log min(m, n)) — the binary search runs over 0..m of the shorter list, and each round does a constant amount of work. Space O(1) — only a few numbers, no merged list. (The swap is a single recursive call that happens at most once.)

Input size → what is feasible: m + n up to 10⁵ and one query → merging is fine; 10⁴ queries on lists of 10⁶ → only the partition search fits; with m = 2 and n = 10⁶ it takes just 2 rounds.

Common mistakes. (1) Searching the longer list: j can fall outside 0..n and the code reads past the end. (2) Forgetting the −∞ / +∞ ends — a[i − 1] with i = 0 throws a RangeError. (3) half = (m + n) ~/ 2 while returning the left maximum for an odd total: then the median sits on the right, so you would need min(aRight, bRight) instead — choose one convention and stick to it. (4) Integer division for the even case: (x + y) ~/ 2 turns 5.5 into 5; the answer is a double, so use /. (5) Both lists empty: there is no median — check first, as the Dart code does.

Follow-ups interviewers ask. The k-th smallest of two sorted lists — the same partition with i + j = k (p05-q24). The median of a matrix whose rows are sorted (p05-q26). A stream of numbers with a running median — two heaps (C06 · Heapsort & Priority Queues). The k-th smallest of many sorted lists — binary search on the value and count with one lower bound per list.

The idea underneath: medians and order statistics in C09 · Medians & Order Statistics, merging two sorted lists in C02 · Insertion & Merge Sort, and binary search on a monotonic test from the opening section.

Quiz

Interview questions

Variations and follow-ups of the six problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow reference.

Cheat sheet

Problem	What is searched	Loop	Time	Space	The decision at mid
Binary Search	indexes 0..n − 1	`lo ≤ hi`	O(log n)	O(1)	equal → found; smaller → `lo = mid + 1`; bigger → `hi = mid − 1`
Search a 2D Matrix	positions 0..rows·cols − 1	`lo ≤ hi`	O(log(rc))	O(1)	read `matrix[mid ~/ cols][mid % cols]`, then as above
Koko Eating Bananas	speeds 1..max(piles)	`lo < hi`	O(n log M)	O(1)	hours(mid) ≤ h → `hi = mid`; else `lo = mid + 1`; hours use `(p + k − 1) ~/ k`
Rotated minimum	indexes 0..n − 1	`lo < hi`	O(log n)	O(1)	nums[mid] > nums[hi] → `lo = mid + 1`; else `hi = mid`
Rotated search	indexes 0..n − 1	`lo ≤ hi`	O(log n)	O(1)	nums[lo] ≤ nums[mid] → left half sorted, test its ends; else right half sorted, test its ends
Median of two lists	cut i in 0..m of the shorter list	`lo ≤ hi`	O(log min(m, n))	O(1)	aLeft > bRight → `hi = i − 1`; bLeft > aRight → `lo = i + 1`; else done

Template	Shape	Use when
Find exact (closed)	`lo = 0, hi = n − 1; while (lo <= hi)` … `lo = mid + 1` / `hi = mid − 1`; −1 after the loop	"is it here, and where?"
Lower bound	`lo = 0, hi = n; while (lo < hi)`: `a[mid] < x` → `lo = mid + 1`, else `hi = mid`	first ≥ x, insert position, first copy
Upper bound	same with `a[mid] <= x`	first > x, one past the last copy; count = upper − lower
First true (on the answer)	`ok(mid)` → `hi = mid`, else `lo = mid + 1`; `ok(hi)` must be true	smallest speed / capacity / day that works
Last true	round up: `mid = lo + (hi − lo + 1) ~/ 2`; `ok(mid)` → `lo = mid`, else `hi = mid − 1`	largest gap / square root / full rows that fit
Real numbers	repeat 60 times: `mid = (lo + hi) / 2`; keep the half that holds the answer	averages, times, roots to a tolerance

Always mid = lo + (hi - lo) ~/ 2. If the range can stay the same size after a move, the loop never ends — check that every branch shrinks it. Binary search needs sorted data or a test that flips once; otherwise use hashing (Step 13.1 · Arrays & Hashing) or two pointers (Step 13.2 · Two Pointers).