Binary Search on Two Sorted Arrays and Matrices
A sorted matrix is one long row
Search a 2D Matrix gives you a grid where every row is sorted and each row's first value is bigger than the last value of the row before it:
[[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
Is 16 in it? Checking every cell works, but on a 1,000 × 1,000 grid that's a million looks. A binary search on each row is better, about 10,000. But one binary search is enough.
Read the grid row by row: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. Each row picks up where the one before it left off, so that's one sorted list of 12 values, and you don't even have to build it. Position p in it is row p ÷ 4, rounded down, and column p % 4, the remainder; 4 is the number of columns. Position 6 is row 1, column 2, and that cell holds 16.
![Search a 2D Matrix on the grid [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]. Each row is drawn in its own color, and the same twelve values appear again below as one strip, row 0 then row 1 then row 2, with positions 0 to 11. The strip is sorted because each row's first value is bigger than the last value of the row before. The value 16 is marked in both: it's position 6 in the strip and row 1, column 2 in the grid, since 6 divided by 4 columns is 1 with 2 left over.](https://pub-a1b3030acfb94e84ba8a89fb182c53bc.r2.dev/public/dsa-content-db82c6a5-c34b-4fc1-b6c8-cfff3860e373/one-long-row.webp)
One binary search over the positions
So the search is the value loop from Introduction to Binary Search, run over positions 0 to rows × cols − 1, with one extra line that turns mid into a cell:
Searching the grid for 16 — Each step looks at the middle position and the cell it stands for. Dark cells are positions the search has ruled out.
bool searchMatrix(const vector<vector<int>>& matrix, int target) {
int rows = matrix.size(), cols = matrix[0].size();
int lo = 0, hi = rows * cols - 1; // positions, reading the matrix row by row
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int value = matrix[mid / cols][mid % cols]; // position mid: row mid / cols, column mid % cols
if (value == target) return true;
if (value < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
def search_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols - 1 # positions, reading the matrix row by row
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols] # position mid: row mid // cols, column mid % cols
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
static boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length;
int lo = 0, hi = rows * cols - 1; // positions, reading the matrix row by row
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int value = matrix[mid / cols][mid % cols]; // position mid: row mid / cols, column mid % cols
if (value == target) return true;
if (value < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
function searchMatrix(matrix, target) {
const rows = matrix.length, cols = matrix[0].length;
let lo = 0, hi = rows * cols - 1; // positions, reading the matrix row by row
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
const value = matrix[Math.floor(mid / cols)][mid % cols]; // row mid / cols, column mid % cols
if (value === target) return true;
if (value < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
Each prints true, false, true, false and true for 16, 13, 60 and 0 in the grid above, then 5 in [[5]]. The search looks at 3 cells to find 16 and never more than 4 in this grid; a million-cell grid takes at most 20. That's O(log(m · n)) time and no extra space.
When only rows and columns are sorted
Search a 2D Matrix II promises less. Each row is sorted left to right and each column top to bottom, but a row's first value can be smaller than the last value of the row above:
[[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
Row 0 ends at 15 and row 1 starts at 2, so reading row by row isn't sorted any more, and the long-row trick is gone.
Start at the top-right corner instead. Everything to its left is smaller, and everything below it is bigger. So one comparison with the target rules out a whole line:
- The corner is bigger than the target. Everything below it is bigger still, so the target isn't in this column. Step left.
- The corner is smaller. Everything to its left is smaller still, so the target isn't in this row. Step down.
Each step drops a row or a column, so the walk ends within rows + cols steps.
Walking the grid for 14 — The glowing cell is the current corner. Each step rules out its column (step left) or its row (step down), shown in dark.
bool searchMatrix(const vector<vector<int>>& matrix, int target) {
int row = 0, col = matrix[0].size() - 1; // start at the top-right corner
while (row < (int)matrix.size() && col >= 0) {
int value = matrix[row][col];
if (value == target) return true;
if (value > target) col--; // everything below is bigger too: drop this column
else row++; // everything to the left is smaller too: drop this row
}
return false;
}
def search_matrix(matrix, target):
row, col = 0, len(matrix[0]) - 1 # start at the top-right corner
while row < len(matrix) and col >= 0:
value = matrix[row][col]
if value == target:
return True
if value > target:
col -= 1 # everything below is bigger too: drop this column
else:
row += 1 # everything to the left is smaller too: drop this row
return False
static boolean searchMatrix(int[][] matrix, int target) {
int row = 0, col = matrix[0].length - 1; // start at the top-right corner
while (row < matrix.length && col >= 0) {
int value = matrix[row][col];
if (value == target) return true;
if (value > target) col--; // everything below is bigger too: drop this column
else row++; // everything to the left is smaller too: drop this row
}
return false;
}
function searchMatrix(matrix, target) {
let row = 0, col = matrix[0].length - 1; // start at the top-right corner
while (row < matrix.length && col >= 0) {
const value = matrix[row][col];
if (value === target) return true;
if (value > target) col--; // everything below is bigger too: drop this column
else row++; // everything to the left is smaller too: drop this row
}
return false;
}
Each prints true, false, true, true and false for 14, 20, 5, 30 and 0.
This isn't binary search. It's two pointers, one on the rows and one on the columns, and it's the same elimination as Two Sum II - Input Array Is Sorted: each comparison rules out a whole line of candidates. It costs O(m + n). A binary search on every row costs O(m log n): about 10,000 looks on a 1,000 × 1,000 grid, against at most 2,000 steps. Only on a very flat grid, say 10 rows of 100,000, do the row searches win: about 170 looks against up to 100,010 steps.
Why the top-right corner? From the top-left, right and down both lead to bigger values, so comparing with the target can't rule anything out. The bottom-left corner works too: up is smaller and right is bigger.
Two sorted arrays: search the cut
Kth Element of Two Sorted Arrays: a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10, 11], and you want the 5th smallest value of the two together. Merging them the way merge sort does and stopping at the 5th value works: 1, 2, 3, 4, 6, so it's 6. But that's up to k steps, 20,000 when each array holds 10,000 values, and binary search can do it in about 14. There's no single sorted array to search, though. So search something else.
The 5 smallest values are a few from the front of a and the rest from the front of b. Say i of them come from a; then k − i come from b. Choose i and everything is fixed: i = 3 takes 2, 3, 6 from a and 1, 4 from b. Think of it as one cut through each array.
When is a cut right? Every value taken has to be at most every value left out. Inside each array that's free, because it's sorted. So only two comparisons cross between the arrays:
- a's last taken value is at most b's first value left out (6 ≤ 8), and
- b's last taken value is at most a's first value left out (4 ≤ 7).
Now turn it into a yes/no question that flips once. Ask: is b's last taken value at most a's first value left out? In code that's b[k - i - 1] <= a[i]: b gives k − i values, so its last taken one is b[k − i − 1], and a's first value left out is a[i]. A no means a[i] was left out while something bigger was taken from b: you took too few from a. Taking one more from a can only raise a's first value left out and lower b's last taken value, so once the answer is yes, it stays yes. That's the first-yes loop from Introduction to Binary Search, run over i.
And the first yes is the right cut. The second comparison holds there because it's the question itself. The first one holds because taking one fewer from a was a no, and that no says exactly that a's last taken value is smaller than b's first value left out. At the very bottom of the range there's no cut with one fewer, but there the first comparison has nothing to fail on: either nothing is taken from a, or nothing of b is left out.
The range of i: you can't take more than k, or more than a holds, so hi = min(k, len(a)). And b holds only len(b) values, so at least k − len(b) must come from a: lo = max(0, k - len(b)). Inside the loop i stays below hi, so a[i] and b[k − i − 1] always exist and need no special cases. When the loop ends, the kth smallest is the larger of the two last taken values.
Searching the cut for the 5th smallest — Row 0 is a and row 1 is b. Violet cells are taken; the two amber cells are the values the question compares.
int countFromA(const vector<int>& a, const vector<int>& b, int k) {
int m = a.size(), n = b.size();
int lo = max(0, k - n), hi = min(k, m); // b can give at most n values, a at most m
while (lo < hi) {
int i = lo + (hi - lo) / 2; // try i from a and k - i from b
if (b[k - i - 1] <= a[i]) hi = i; // yes: enough from a, maybe fewer works
else lo = i + 1; // no: a[i] beats b's last taken value, take more from a
}
return lo;
}
int kthElement(const vector<int>& a, const vector<int>& b, int k) {
int i = countFromA(a, b, k), j = k - i; // the k smallest: the first i of a, the first j of b
if (i == 0) return b[j - 1]; // all k come from b
if (j == 0) return a[i - 1]; // all k come from a
return max(a[i - 1], b[j - 1]); // the larger last taken value
}
def count_from_a(a, b, k):
lo, hi = max(0, k - len(b)), min(k, len(a)) # b can give at most len(b) values, a at most len(a)
while lo < hi:
i = (lo + hi) // 2 # try i from a and k - i from b
if b[k - i - 1] <= a[i]:
hi = i # yes: enough from a, maybe fewer works
else:
lo = i + 1 # no: a[i] beats b's last taken value, take more from a
return lo
def kth_element(a, b, k):
i = count_from_a(a, b, k)
j = k - i # the k smallest: the first i of a, the first j of b
if i == 0:
return b[j - 1] # all k come from b
if j == 0:
return a[i - 1] # all k come from a
return max(a[i - 1], b[j - 1]) # the larger last taken value
static int countFromA(int[] a, int[] b, int k) {
int m = a.length, n = b.length;
int lo = Math.max(0, k - n), hi = Math.min(k, m); // b can give at most n values, a at most m
while (lo < hi) {
int i = lo + (hi - lo) / 2; // try i from a and k - i from b
if (b[k - i - 1] <= a[i]) hi = i; // yes: enough from a, maybe fewer works
else lo = i + 1; // no: a[i] beats b's last taken value, take more from a
}
return lo;
}
static int kthElement(int[] a, int[] b, int k) {
int i = countFromA(a, b, k), j = k - i; // the k smallest: the first i of a, the first j of b
if (i == 0) return b[j - 1]; // all k come from b
if (j == 0) return a[i - 1]; // all k come from a
return Math.max(a[i - 1], b[j - 1]); // the larger last taken value
}
function countFromA(a, b, k) {
const m = a.length, n = b.length;
let lo = Math.max(0, k - n), hi = Math.min(k, m); // b can give at most n values, a at most m
while (lo < hi) {
const i = lo + Math.floor((hi - lo) / 2); // try i from a and k - i from b
if (b[k - i - 1] <= a[i]) hi = i; // yes: enough from a, maybe fewer works
else lo = i + 1; // no: a[i] beats b's last taken value, take more from a
}
return lo;
}
function kthElement(a, b, k) {
const i = countFromA(a, b, k), j = k - i; // the k smallest: the first i of a, the first j of b
if (i === 0) return b[j - 1]; // all k come from b
if (j === 0) return a[i - 1]; // all k come from a
return Math.max(a[i - 1], b[j - 1]); // the larger last taken value
}
Each prints 6, 10, 5, 2 and 3: k = 5 on the arrays above, the problem's two examples, then two edges. With k = 1 everything comes from b, and with [1, 2, 3], [10, 20] and k = 3 everything comes from a.
The loop tries at most min(m, n) + 1 values of i, so it's O(log min(m, n)) time and no extra space. You'll often see this written with a swap that puts the shorter array first. The bounds above already keep the range that small, so the swap isn't needed.
Median of Two Sorted Arrays
The median is a kth smallest value. With m + n values in all, cut at k = (m + n + 1) / 2, rounded down:
- An odd total. The median is the kth value: the larger of the two last taken values.
- An even total. It's the average of the kth and the (k + 1)th values, and the same cut gives you the (k + 1)th for free: the smaller of the two first values left out.
On [1, 2] and [3, 4], k = 2 takes 1 and 2 and leaves out 3 and 4, so the median is (2 + 3) / 2 = 2.5. Either array can be empty. The bounds then allow only one cut, and the loop doesn't run.
The code reuses count_from_a (countFromA) from the previous section:
double findMedianSortedArrays(const vector<int>& a, const vector<int>& b) {
int m = a.size(), n = b.size();
int k = (m + n + 1) / 2; // the middle value, or the lower of the two middles
int i = countFromA(a, b, k), j = k - i;
int left = max(i > 0 ? a[i - 1] : INT_MIN, j > 0 ? b[j - 1] : INT_MIN); // the largest value taken
if ((m + n) % 2 == 1) return left;
int right = min(i < m ? a[i] : INT_MAX, j < n ? b[j] : INT_MAX); // the smallest value left out
return (left + right) / 2.0;
}
from math import inf
def find_median_sorted_arrays(a, b):
total = len(a) + len(b)
k = (total + 1) // 2 # the middle value, or the lower of the two middles
i = count_from_a(a, b, k)
j = k - i
left = max(a[i - 1] if i > 0 else -inf, b[j - 1] if j > 0 else -inf) # the largest value taken
if total % 2 == 1:
return float(left)
right = min(a[i] if i < len(a) else inf, b[j] if j < len(b) else inf) # the smallest value left out
return (left + right) / 2
static double findMedianSortedArrays(int[] a, int[] b) {
int m = a.length, n = b.length;
int k = (m + n + 1) / 2; // the middle value, or the lower of the two middles
int i = countFromA(a, b, k), j = k - i;
// the largest value taken, and for an even total the smallest value left out
int left = Math.max(i > 0 ? a[i - 1] : Integer.MIN_VALUE, j > 0 ? b[j - 1] : Integer.MIN_VALUE);
if ((m + n) % 2 == 1) return left;
int right = Math.min(i < m ? a[i] : Integer.MAX_VALUE, j < n ? b[j] : Integer.MAX_VALUE);
return (left + right) / 2.0;
}
function findMedianSortedArrays(a, b) {
const m = a.length, n = b.length;
const k = Math.floor((m + n + 1) / 2); // the middle value, or the lower of the two middles
const i = countFromA(a, b, k), j = k - i;
const left = Math.max(i > 0 ? a[i - 1] : -Infinity, j > 0 ? b[j - 1] : -Infinity); // the largest taken
if ((m + n) % 2 === 1) return left;
const right = Math.min(i < m ? a[i] : Infinity, j < n ? b[j] : Infinity); // the smallest left out
return (left + right) / 2;
}
Each prints 2.0, 2.5, 1.0, 2.0 and 3.0 for [1, 3] with [2], [1, 2] with [3, 4], [] with [1], [2] with [] and [-5, 3, 6, 12, 15] with [-12, -10, -6, -3, 4, 10]. It's O(log min(m, n)), the time the problem asks for. In C++ and Java, divide by 2.0, not 2: on two ints, (2 + 3) / 2 is 2.
Median in a Row-wise Sorted Matrix: search the value
Now only the rows are sorted: [[1, 3, 5], [2, 6, 9], [3, 6, 9]]. You can't read it as one row, and with 3 rows instead of two arrays there's no single cut. Go back to Binary Search on the Answer and search the value itself.
Pick a value x and count how many values are at most x. In a sorted row that count is the upper bound from Introduction to Binary Search, one binary search per row; add the rows up. The count only grows as x grows, so "are at least half the values at most x?" flips once, and the median is the first yes: the smallest x with a count of at least (9 + 1) / 2 = 5. At x = 4 the rows count 2 + 1 + 1 = 4, a no. At x = 5 they count 3 + 1 + 1 = 5, a yes. So the median is 5.
The bounds are the smallest first value and the largest last value. And the answer is always a value in the matrix: between two neighbouring values the count doesn't change, so it can first reach 5 only at a value that's there.
Binary search over the values — The row is the possible medians. Each step counts the values at most x: green when that's at least half, amber when it isn't.
int matrixMedian(const vector<vector<int>>& mat) {
int rows = mat.size(), cols = mat[0].size();
int need = (rows * cols + 1) / 2; // the median has at least this many values <= it
int lo = INT_MAX, hi = INT_MIN;
for (const auto& row : mat) {
lo = min(lo, row.front()); // the smallest value is some row's first
hi = max(hi, row.back()); // the largest is some row's last
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = 0;
for (const auto& row : mat) // values <= mid: an upper bound in each row
count += upper_bound(row.begin(), row.end(), mid) - row.begin();
if (count >= need) hi = mid; // yes: the median is mid or smaller
else lo = mid + 1; // no: fewer than half are <= mid
}
return lo;
}
from bisect import bisect_right
def matrix_median(mat):
need = (len(mat) * len(mat[0]) + 1) // 2 # the median has at least this many values <= it
lo = min(row[0] for row in mat) # the smallest value is some row's first
hi = max(row[-1] for row in mat) # the largest is some row's last
while lo < hi:
mid = (lo + hi) // 2
count = sum(bisect_right(row, mid) for row in mat) # values <= mid: an upper bound in each row
if count >= need:
hi = mid # yes: the median is mid or smaller
else:
lo = mid + 1 # no: fewer than half are <= mid
return lo
static int countAtMost(int[] row, int x) { // the upper bound: how many values are <= x
int lo = 0, hi = row.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (row[mid] > x) hi = mid;
else lo = mid + 1;
}
return lo;
}
static int matrixMedian(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int need = (rows * cols + 1) / 2; // the median has at least this many values <= it
int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
for (int[] row : mat) {
lo = Math.min(lo, row[0]); // the smallest value is some row's first
hi = Math.max(hi, row[cols - 1]); // the largest is some row's last
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = 0;
for (int[] row : mat) count += countAtMost(row, mid);
if (count >= need) hi = mid; // yes: the median is mid or smaller
else lo = mid + 1; // no: fewer than half are <= mid
}
return lo;
}
function countAtMost(row, x) { // the upper bound: how many values are <= x
let lo = 0, hi = row.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (row[mid] > x) hi = mid;
else lo = mid + 1;
}
return lo;
}
function matrixMedian(mat) {
const need = Math.floor((mat.length * mat[0].length + 1) / 2); // at least this many values <= the median
let lo = Infinity, hi = -Infinity;
for (const row of mat) {
lo = Math.min(lo, row[0]); // the smallest value is some row's first
hi = Math.max(hi, row[row.length - 1]); // the largest is some row's last
}
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
let count = 0;
for (const row of mat) count += countAtMost(row, mid);
if (count >= need) hi = mid; // yes: the median is mid or smaller
else lo = mid + 1; // no: fewer than half are <= mid
}
return lo;
}
Each prints 5, 6, 4 and 1 for the matrix above, [[2, 4, 9], [3, 6, 7], [4, 7, 10]], [[3], [4], [8]] and [[1, 1, 1], [1, 1, 1], [1, 1, 2]].
Each count is one binary search per row, O(r log c), and the loop counts about log₂(range) times, so it's O(r · log c · log(range)). On a 400 × 400 matrix of values up to 2,000 that's about 40,000 steps, against sorting all 160,000 values.
Which one to use
Ask what exactly is sorted:
- One sorted run in disguise: each row picks up where the one before it left off. Search the positions as one array, O(log(m · n)).
- Rows and columns both sorted, and you want a value: walk from the top-right (or bottom-left) corner, O(m + n). Not binary search at all.
- Two sorted arrays, and you want the kth value or the median: binary search the cut, O(log min(m, n)).
- Many sorted rows, and you want the kth value or the median: binary search the value and count each row, O(r · log c · log(range)). When the columns are sorted too, the corner walk counts the whole matrix in O(m + n).
Near misses: if the problem wants the merged array itself, just merge in O(m + n); there's nothing to search. And a grid whose rows are sorted but don't pick up where the one before left off can't be searched as one long row: check that promise before you flatten.
Common mistakes
Dividing by the number of rows. matrix[mid // rows][mid % rows]
On the 3 × 4 grid it says False for 20, which is right there, and searching for 60 crashes with IndexError: list index out of range. Every row holds cols values, so position p is in row p // cols. The two agree only on square grids, which is why the bug survives a square test.
Reading a[i − 1] when nothing comes from a. The if i == 0 check missing
On [5, 10, 15], [2, 6, 12, 20, 25] and k = 1 it returns 15, not 2. In Python, a[-1] doesn't crash: it reads the last value, so the bug hides as a wrong answer. In C++ it reads memory outside the array.
Starting the cut at 0. lo = 0 instead of max(0, k - len(b))
On [1, 2, 3, 4, 5, 6], [7] and k = 6 it crashes with IndexError: list index out of range. The first i it tries is 3, which leaves 3 to take from b, and b holds 1.
Dividing ints in the median. return (left + right) / 2; in Java
On [1, 2] and [3, 4] it returns 2.0, not 2.5. Both are ints, so the division drops the half before the result becomes a double. Divide by 2.0.
Counting values below x instead of at most x. bisect_left instead of bisect_right
On [[1, 3, 5], [2, 6, 9], [3, 6, 9]] it returns 6, not 5. At x = 5 it counts only the 4 values below 5, so 5 looks like a no.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Search a 2D Matrix: one binary search over the positions.
- Search a 2D Matrix II: the walk from the top-right corner.
- Kth Element of Two Sorted Arrays: binary search the cut.
- Median of Two Sorted Arrays: the same cut at k = (m + n + 1) / 2.
- Median in a Row-wise Sorted Matrix: binary search the value and count each row.
That's the whole Binary Search section. The Binary Search Quiz checks all four lessons.