These are the notes for DSA episode 15, the last episode of the binary search block, and its most famous hard problem: Median of Two Sorted Arrays (LeetCode 4). We solve a slightly bigger problem, the k-th smallest value of two sorted arrays, because the median is just k = the middle, and it also answers "what is the value at combined rank k?" The brute force merges with two pointers and costs O(m + n) per question; with one lakh rank questions on twenty lakh values it times out. The optimal solution binary searches on how many values to take from the smaller array (the cut): O(log(min(m, n))). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Two state boards publish their results, and each list is sorted by score. A national college admits students from both, so it needs one combined ranking. It keeps asking: what is the median score of all applicants? What is the score at combined rank 5,000? At rank 20,000? Building the merged list again for every question is wasteful.
Problem statement
Given two sorted arrays a (length m) and b (length n), return the median of all m + n values. The median is the middle value of the merged sorted list; with an even count it is the average of the two middle values. Required: O(log(m + n)) time.
| a | b | merged | median |
|---|---|---|---|
| [1, 3] | [2] | 1, 2, 3 | 2.0 |
| [1, 2] | [3, 4] | 1, 2, 3, 4 | (2 + 3) / 2 = 2.5 |
| [1, 3, 8, 9, 15] | [7, 11, 18, 19, 21, 25] | 1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25 | 11.0 |
| [] | [5] | 5 | 5.0 |
| [-5, -3] | [-4] | -5, -4, -3 | -4.0 |
| [1, 2, 3] | [10, 20, 30, 40] | 1, 2, 3, 10, 20, 30, 40 | 10.0 |
The general version: kth(a, b, k) = the k-th smallest value (1-based). With total t = m + n:
todd → median =kth(t / 2 + 1)teven → median =(kth(t / 2) + kth(t / 2 + 1)) / 2.0
Solution 1: brute force (merge and walk)
This is the merge step of merge sort: two pointers i in a and j in b; take the smaller front value, k times. The last value taken is the k-th smallest.
public class Main {
static int kth(int[] a, int[] b, int k) {
int i = 0, j = 0, x = 0;
while (k-- > 0)
x = (j == b.length || i < a.length && a[i] <= b[j]) ? a[i++] : b[j++];
return x;
}
static double median(int[] a, int[] b) {
int t = a.length + b.length;
if (t % 2 == 1) return kth(a, b, t / 2 + 1);
return (kth(a, b, t / 2) + (long) kth(a, b, t / 2 + 1)) / 2.0;
}
public static void main(String[] args) {
System.out.println(median(new int[]{1, 3}, new int[]{2}));
System.out.println(median(new int[]{1, 2}, new int[]{3, 4}));
}
}
Output:
2.0
2.5
Now the college: ten lakh scores from each board and one lakh rank questions.
int n = 1000000, q = 100000;
int[] a = new int[n], b = new int[n];
for (int i = 0; i < n; i++) { a[i] = 2 * i; b[i] = 2 * i + 1; }
long t0 = System.nanoTime(), sum = 0;
for (int r = 1; r <= q; r++)
sum += kth(a, b, (int) (r * 7919L % (2 * n)) + 1);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(sum + " " + ms + " ms");
Result: Time Limit Exceeded. Each question walks up to 20 lakh steps from the start.
Why it is slow
- The merge walk is O(k), up to O(m + n), per question.
- Even a single median is O(m + n): linear, not log.
- It looks at every value below rank
kone by one, like a linear scan, even though both lists are sorted.
The key insight: the k smallest are two prefixes
Take a = [1, 3, 8, 9, 15], b = [7, 11, 18, 19, 21, 25]: 11 values, so the median is the 6th smallest.
The 6 smallest values, whatever they are, must be some values from the front of a plus some values from the front of b: in a sorted array a small value never hides behind a big one. So there is only one free choice: take i values from a, and then j = k - i from b is forced. This choice is called the cut (or partition).
Look at the four values next to the cut:
| name | value | meaning |
|---|---|---|
aL |
a[i - 1] |
last value taken from a |
aR |
a[i] |
first value left in a |
bL |
b[j - 1] |
last value taken from b |
bR |
b[j] |
first value left in b |
Inside each array the left side is already <= the right side (it is sorted). So the cut is correct exactly when the cross pairs are fine too:
aL <= bRandbL <= aR→ correct; the k-th smallest ismax(aL, bL).aL > bR→ we took a value fromabigger than one left inb: too many from a, makeismaller.bL > aR→ too few from a, makeibigger.
That is monotonic in i, so we binary search on i. If a side is empty (i == 0, i == m, j == 0, j == n) use sentinels: Integer.MIN_VALUE for a missing left value (it never wins the max) and Integer.MAX_VALUE for a missing right value.
Two details:
- Binary search on the smaller array (swap if
ais longer): O(log(min(m, n))) steps. - Bounds:
j = k - imust fit inb(0 <= j <= n), solo = max(0, k - n)andhi = min(k, m).
Dry run: kth(a, b, 6)
| Step | lo | hi | i | j | aL | aR | bL | bR | Check | Action |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 4 | 3 | 8 | 19 | 21 | bL 19 > aR 8 | too few from a: lo = 3 |
| 2 | 3 | 5 | 4 | 2 | 9 | 15 | 11 | 18 | 9 <= 18, 11 <= 15 | correct: max(9, 11) = 11 |
Check by hand: 1, 3, 7, 8, 9, 11. Two steps.
Solution 2: the optimal solution, typed live
public class Main {
static int kth(int[] a, int[] b, int k) {
if (a.length > b.length) return kth(b, a, k);
int m = a.length, n = b.length;
int lo = Math.max(0, k - n), hi = Math.min(k, m);
while (lo <= hi) {
int i = lo + (hi - lo) / 2, j = k - i;
int aL = i == 0 ? Integer.MIN_VALUE : a[i - 1];
int aR = i == m ? Integer.MAX_VALUE : a[i];
int bL = j == 0 ? Integer.MIN_VALUE : b[j - 1];
int bR = j == n ? Integer.MAX_VALUE : b[j];
if (aL > bR) hi = i - 1;
else if (bL > aR) lo = i + 1;
else return Math.max(aL, bL);
}
return -1;
}
static double median(int[] a, int[] b) {
int t = a.length + b.length;
if (t % 2 == 1) return kth(a, b, t / 2 + 1);
return (kth(a, b, t / 2) + (long) kth(a, b, t / 2 + 1)) / 2.0;
}
public static void main(String[] args) {
System.out.println(median(new int[]{1, 3}, new int[]{2}));
System.out.println(median(new int[]{1, 2}, new int[]{3, 4}));
System.out.println(median(new int[]{1, 3, 8, 9, 15}, new int[]{7, 11, 18, 19, 21, 25}));
System.out.println(median(new int[0], new int[]{5}));
System.out.println(median(new int[]{-5, -3}, new int[]{-4}));
System.out.println(median(new int[]{1, 2, 3}, new int[]{10, 20, 30, 40}));
System.out.println(kth(new int[]{1, 3, 8}, new int[]{7, 11}, 1));
System.out.println(kth(new int[]{1, 3, 8}, new int[]{7, 11}, 5));
}
}
Output:
2.0
2.5
11.0
5.0
-4.0
10.0
1
11
All eight are correct (both examples, the 11-value example, an empty array, negatives, a short a with a long b, and the first and last rank). The college's one lakh questions on twenty lakh scores printed:
99985950000 36 ms
The same total as the walk would give; each question takes about 20 steps.
The same solution in C++ and Python
#include <bits/stdc++.h>
using namespace std;
int kth(const vector<int>& a, const vector<int>& b, int k) { // k-th smallest, 1-based
if (a.size() > b.size()) return kth(b, a, k);
int m = a.size(), n = b.size();
int lo = max(0, k - n), hi = min(k, m);
while (lo <= hi) {
int i = lo + (hi - lo) / 2, j = k - i;
int aL = i == 0 ? INT_MIN : a[i - 1];
int aR = i == m ? INT_MAX : a[i];
int bL = j == 0 ? INT_MIN : b[j - 1];
int bR = j == n ? INT_MAX : b[j];
if (aL > bR) hi = i - 1;
else if (bL > aR) lo = i + 1;
else return max(aL, bL);
}
return -1;
}
double median(const vector<int>& a, const vector<int>& b) {
int t = a.size() + b.size();
if (t % 2 == 1) return kth(a, b, t / 2 + 1);
return ((long long)kth(a, b, t / 2) + kth(a, b, t / 2 + 1)) / 2.0;
}
int main() {
cout << median({1, 3}, {2}) << " " << median({1, 2}, {3, 4}) << " "
<< median({1, 3, 8, 9, 15}, {7, 11, 18, 19, 21, 25}) << " " << median({}, {5}) << " "
<< median({-5, -3}, {-4}) << " " << median({1, 2, 3}, {10, 20, 30, 40}) << "\n";
}
Output (C++ prints doubles without a trailing .0):
2 2.5 11 5 -4 10
INF = float("inf")
def kth(a, b, k): # k-th smallest, 1-based
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
lo, hi = max(0, k - n), min(k, m)
while lo <= hi:
i = (lo + hi) // 2
j = k - i
aL = a[i - 1] if i > 0 else -INF
aR = a[i] if i < m else INF
bL = b[j - 1] if j > 0 else -INF
bR = b[j] if j < n else INF
if aL > bR:
hi = i - 1
elif bL > aR:
lo = i + 1
else:
return max(aL, bL)
def median(a, b):
t = len(a) + len(b)
if t % 2 == 1:
return float(kth(a, b, t // 2 + 1))
return (kth(a, b, t // 2) + kth(a, b, t // 2 + 1)) / 2
print(median([1, 3], [2]), median([1, 2], [3, 4]), median([1, 3, 8, 9, 15], [7, 11, 18, 19, 21, 25]),
median([], [5]), median([-5, -3], [-4]), median([1, 2, 3], [10, 20, 30, 40]))
Output:
2.0 2.5 11.0 5.0 -4.0 10.0
The classic single-cut version
Interviewers often expect one cut with left size half = (m + n + 1) / 2; the median then comes from the four neighbours directly:
static double median(int[] a, int[] b) {
if (a.length > b.length) return median(b, a);
int m = a.length, n = b.length, half = (m + n + 1) / 2;
int lo = 0, hi = m;
while (lo <= hi) {
int i = lo + (hi - lo) / 2, j = half - i;
int aL = i == 0 ? Integer.MIN_VALUE : a[i - 1];
int aR = i == m ? Integer.MAX_VALUE : a[i];
int bL = j == 0 ? Integer.MIN_VALUE : b[j - 1];
int bR = j == n ? Integer.MAX_VALUE : b[j];
if (aL > bR) hi = i - 1;
else if (bL > aR) lo = i + 1;
else if ((m + n) % 2 == 1) return Math.max(aL, bL);
else return (Math.max(aL, bL) + (long) Math.min(aR, bR)) / 2.0;
}
return -1;
}
It printed 2.0, 2.5, 11.0 and 3.5 for the examples and the quiz. Because a is the smaller array, j = half - i is always between 0 and n, so lo = 0, hi = m is safe here.
Three bugs, three real failures
Bug 1: no bounds on i
int lo = 0, hi = k;
median(new int[]{1}, new int[]{2, 3, 4, 5, 6, 7}) crashed:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
at Main.kth(Main.java:8)
k = 4, so the first i is 2, but a has only one element. Keep lo = max(0, k - n), hi = min(k, m).
Bug 2: lazy sentinels
Using 0 instead of Integer.MIN_VALUE / Integer.MAX_VALUE for an empty side: median(new int[]{-1}, new int[]{-9, -8}) printed 0.0 (should be -8.0). With negative numbers a fake 0 on the left is bigger than every real value, so it wins the max.
Bug 3: int overflow in the average
return (kth(a, b, t / 2) + kth(a, b, t / 2 + 1)) / 2.0;
median(new int[]{2147483647}, new int[]{2147483647}) printed -1.0. The two ints overflowed before the division (2147483647 + 2147483647 wraps to -2). Cast one side to long.
Complexity
| Approach | Time per question | Extra space | 10⁵ questions on 2 × 10⁶ values |
|---|---|---|---|
| Concatenate and sort | O((m + n) log(m + n)) | O(m + n) | far too slow |
| Merge and walk | O(m + n) | O(1) (O(m + n) if you build the merged array) | Time Limit Exceeded |
| Binary search on the cut | O(log(min(m, n))) | O(1) | 36 ms |
median calls kth at most twice, so the complexity is the same.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
int lo = 0, hi = k; |
ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1 |
i or j outside its array |
lo = max(0, k - n), hi = min(k, m) |
i == 0 ? 0 : a[i - 1] |
median({-1}, {-9, -8}) = 0.0 |
a fake 0 beats negatives | Integer.MIN_VALUE / Integer.MAX_VALUE |
(kth(..) + kth(..)) / 2.0 |
median({2147483647}, {2147483647}) = -1.0 |
int + int overflows first |
cast one side to long |
/ 2 instead of / 2.0 |
median({1, 2}, {3, 4}) = 2.0 |
integer division drops the .5 | divide by 2.0 |
| Searching the longer array without bounds | crashes or wrong cuts | j can go negative or past n |
swap so a is the smaller array |
Mini project: the merit list service
Read two boards' sorted score lists. Answer queries of three kinds: median, rank k (the k-th highest: that is kth(t - k + 1)), and percentile p (the value at rank ceil(p / 100 × t)). Each query is O(log(min(m, n))), with no merged list in memory.
Practice
- Write the median with one cut instead of two
kthcalls.
Solution
See "The classic single-cut version" above: left size (m + n + 1) / 2, and for an even total the median is (max(aL, bL) + min(aR, bR)) / 2.0.
- K-th element of two sorted arrays (GeeksforGeeks).
Solution
That is kth itself. kth({1, 3, 8}, {7, 11}, 1) = 1 and kth({1, 3, 8}, {7, 11}, 5) = 11.
- Why must we binary search the smaller array?
Solution
Speed: the search range is at most min(m, n) + 1 values, so O(log(min(m, n))) steps. Safety in the single-cut version: with a smaller, j = half - i always lands in [0, n]; with a longer, j can go negative.
- Median of a row-wise sorted matrix (every row sorted, odd number of cells).
Solution
Binary search on the value (episode 14's idea): find the first x such that at least r·c/2 + 1 cells are <= x, counting each row with an upper bound.
static int countLE(int[] row, int x) { // how many values <= x
int lo = 0, hi = row.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (row[mid] <= x) lo = mid + 1; else hi = mid;
}
return lo;
}
static int matrixMedian(int[][] g) {
int r = g.length, c = g[0].length, need = r * c / 2 + 1;
int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
for (int[] row : g) { lo = Math.min(lo, row[0]); hi = Math.max(hi, row[c - 1]); }
while (lo < hi) { // first x with count(<= x) >= need
int mid = lo + (hi - lo) / 2, cnt = 0;
for (int[] row : g) cnt += countLE(row, mid);
if (cnt >= need) hi = mid; else lo = mid + 1;
}
return lo;
}
{{1, 3, 5}, {2, 6, 9}, {3, 6, 9}} printed 5. Time O(r · log c · log(range)).
Quick quiz
What does median(new int[]{4, 6}, new int[]{1, 2, 3, 9}) print?
- 3.5
- 4.0
- 3.0
- 5.0
Answer
3.5. Merged: 1, 2, 3, 4, 6, 9. Six values, so the median is the average of the 3rd and 4th smallest: (3 + 4) / 2.0 = 3.5.
Interview questions
- What is the brute force and its cost? Merge with two pointers: O(m + n) time; O(1) space if you only walk, O(m + n) if you build the array.
- What is a "cut" and when is it correct? Taking
ivalues fromaandk - ifromb; correct whenaL <= bRandbL <= aR. - How do you move the cut?
aL > bR→ fewer froma(hi = i - 1);bL > aR→ more froma(lo = i + 1). - Why sentinels, and why MIN/MAX? An empty side must never win:
-∞on the left,+∞on the right.0breaks with negative values. - Complexity? O(log(min(m, n))) time, O(1) space.
- How does this generalise? It is binary search on the answer (episode 14) over the cut position; the same idea gives the k-th smallest, percentiles, and the median of a sorted matrix.
Glossary
| Term | Meaning |
|---|---|
| Median | The middle value of a sorted list; for an even count, the average of the two middle values |
| k-th smallest | The value at position k (1-based) after sorting all values together |
| Merge | Combining two sorted lists into one by repeatedly taking the smaller front value |
| Two pointers | Two indexes moving through arrays, here i in a and j in b |
| Prefix | The first few elements of an array |
| Cut / partition | Splitting both arrays so the left parts together hold exactly k values |
aL, aR, bL, bR |
The values just left and right of the cut in each array |
| Sentinel | A fake value standing in for "nothing here" (Integer.MIN_VALUE, Integer.MAX_VALUE) |
Integer.MIN_VALUE / MAX_VALUE |
The smallest and largest int: -2,147,483,648 and 2,147,483,647 |
| Integer overflow | A result bigger than the type's maximum, which wraps to a wrong value |
| O(log(min(m, n))) | Steps grow with the halvings of the shorter array |
| Binary search on the answer | Searching a range of candidate answers with a monotonic yes/no check (episode 14) |
| Percentile | The value below which a given percentage of all values fall |
Summary
- The k smallest values of two sorted arrays are a prefix of each: choose
ifroma, andj = k - iis forced. - A cut is correct when
aL <= bRandbL <= aR; then the answer ismax(aL, bL). aL > bR→ismaller;bL > aR→ibigger. Binary search on the smaller array, withlo = max(0, k - n),hi = min(k, m).- Sentinels are
Integer.MIN_VALUE/MAX_VALUE, and the average useslongand2.0. - The median is
kth(t / 2 + 1), or the average ofkth(t / 2)andkth(t / 2 + 1). O(log(min(m, n))) time, O(1) space.
Next episode: Sorting 1: bubble, selection, insertion sort.