Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Binary search

Two sorted arrays

Lesson · 13 min read · Binary search · Two sorted arrays

Merging costs O(m + n). Discarding half of what remains, or searching for the right place to cut both arrays, costs a logarithm.

Discarding k / 2 at a time

To find the k-th smallest of two sorted arrays, look at the first k / 2 elements of each. Whichever block ends with the smaller value cannot contain the answer: even if every element of the other block were smaller, those values would rank at most k − 1. Drop that block, subtract its size from k, and repeat.

k-th smallest of two sorted arrays

kth(a, b, k)

  1. If a is used up, the answer is the k-th remaining element of b, and the other way round.
  2. If k = 1, the answer is the smaller of the two front elements.
  3. Take up to k / 2 from the front of each. If a's block ends at a value no larger than b's, drop a's block; otherwise drop b's.
  4. Subtract the number dropped from k and repeat.

The 7th smallest of two arrays; the darker cells are the blocks being compared.

  1. Step 1 / 5
    011529314418525i0213210312420522630j
    k7

    Top row a, bottom row b. We want the 7-th smallest of the two together.

  2. Step 2 / 5
    011529314418525i0213210312420522630j
    k7h3a block end9b block end10

    k = 7, so take up to 3 from each. 9 ≤ 10: the 3 elements of a up to 9 all rank below 7. Drop them; k becomes 4.

  3. Step 3 / 5
    011529314418525i0213210312420522630j
    k4h2a block end18b block end3

    k = 4, so take up to 2 from each. 18 > 3: the 2 elements of b up to 3 all rank below 4. Drop them; k becomes 2.

  4. Step 4 / 5
    011529314418525i0213210312420522630j
    k2h1a block end14b block end10

    k = 2, so take up to 1 from each. 14 > 10: the 1 element of b up to 10 all rank below 2. Drop them; k becomes 1.

  5. Step 5 / 5
    011529314418525i0213210312420522630j
    k1

    k = 1: the answer is the smaller front element, min(14, 12) = 12.

TimeO(log k)
SpaceO(1)

k roughly halves each round. With k up to m + n, that is O(log(m + n)).

The cut

The median splits the merged values into a lower half and an upper half. Any such split takes some prefix of a and some prefix of b. Say the lower half needs L values and takes i from a; then it takes L − i from b. The cut is right when nothing on the left is larger than anything on the right, and because each array is sorted, that is two comparisons:

A cut is right when

valid(i)

  1. a[i − 1] ≤ b[L − i]: the last value taken from a is no larger than the first left behind in b.
  2. b[L − i − 1] ≤ a[i]: the last value taken from b is no larger than the first left behind in a.
  3. Missing elements at either end count as −∞ or +∞.

If the first check fails, i is too large; if the second fails, i is too small. So i is found by binary search over [0, m], and searching the shorter array keeps L − i inside b.

The median of 15 values: the cut that puts 8 values in the lower half.

  1. Step 1 / 4
    030134236339442545011629315417521624728833
    m6n9L8

    15 values, so the lower half holds L = 8. Top: the shorter array a; bottom: b. If the lower half takes i from a, it takes 8 − i from b. Search i in [0, 6].

  2. Step 2 / 4
    030134236339442545i011629315417521624728833j
    lo0i3hi6j5

    i = 3, j = 5: a[2] = 36 > b[5] = 21. The cut takes too much from a: hi = 2.

  3. Step 3 / 4
    030134236339442545i011629315417521624728833j
    lo0i1hi2j7

    i = 1, j = 7: a[0] = 30 > b[7] = 28. The cut takes too much from a: hi = 0.

  4. Step 4 / 4
    030134236339442545i011629315417521624728833j
    i0j8left max28right min30

    i = 0, j = 8: −∞ ≤ 33 and 28 ≤ 30, so the cut is right. The total is odd: the median is the largest on the left, 28.

TimeO(log min(m, n))
SpaceO(1)

The median is then the largest value on the left of the cut when m + n is odd, and the average of that and the smallest value on the right when it is even. The same cut with L = k gives the k-th smallest, so either method answers either problem.

Problems in this module