Find Median in Row-wise Sorted Matrix Using Binary Search

Problem Statement❯

Given a row-wise sorted matrix (each row is individually sorted in increasing order), your task is to find the median of all elements in the matrix.

The matrix contains r rows and c columns.
The total number of elements is always r × c.
If the matrix is empty (0 rows or 0 columns), the median is considered undefined or null.

The median is the element that lies in the middle of the sorted order of all matrix elements. For an odd number of elements, it's the exact middle. For an even number, return the lower middle element.

Examples❯

Matrix	Rows × Cols	Median	Description
[[1, 3, 5], [2, 6, 9], [3, 6, 9]]	3 × 3	5	Sorted order: [1, 2, 3, 3, 5, 6, 6, 9, 9], middle element is 5
[[1, 3], [2, 4]]	2 × 2	2	Sorted: [1, 2, 3, 4], lower middle is 2
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]	3 × 3	5	Already fully sorted matrix, 5 is the center
[[10, 20, 30], [5, 15, 25], [1, 2, 3]]	3 × 3	10	Unordered globally, but each row is sorted. Full order: [1, 2, 3, 5, 10, 15, 20, 25, 30]
[[1]]	1 × 1	1	Only one element
[[1, 2, 3]]	1 × 3	2	Single row
[[1],[2],[3]]	3 × 1	2	Single column
[]	0 × 0	null	Empty matrix, no elements
[[]]	1 × 0	null	One row but zero columns

Visualization Player

Solution❯

How to Find the Median in a Row-wise Sorted Matrix Using Binary Search

The goal is to find the median element in a matrix where each row is sorted in increasing order, but the columns are not necessarily sorted. Since the matrix is not fully sorted, we can't directly flatten and sort it efficiently. Instead, we apply a clever approach using binary search on the value range.

Important: This algorithm only relies on row-wise sorting. Each row is individually sorted in increasing order. Column sorting is not assumed and not needed.

Example Matrix:


  [
    [1, 3, 5],
    [2, 6, 9],
    [3, 6, 9]
  ]

Though rows are sorted, columns are not necessarily sorted (e.g., column 1 is [3,6,6]). That's fine — the logic only looks at rows.

Steps to solve:

Step 1: Identify the minimum and maximum values in the matrix:
- Minimum = smallest first element across rows (because each row is sorted)
- Maximum = largest last element across rows
Step 2: Do a binary search between min and max values, with mid value as the average of min and max values.
Step 3: For each mid value:
- Use binary search in each row to count how many elements are ≤ mid (e.g., with upper_bound)
- Sum the counts across rows
Step 4: If total count ≤ (r * c)/2, median must be larger → low = mid + 1
Step 5: Else, median is smaller or equal → high = mid - 1
Step 6: Repeat until low > high. The value at low is the median.

Example Walkthrough:


  Matrix: 
  [
    [1, 3, 5],
    [2, 6, 9],
    [3, 6, 9]
  ]

  Total elements = 9 (odd), so median is the 5th smallest element.

  min = 1, max = 9
  Binary Search:
    mid = 5 → count = 5 → go left
    mid = 2 → count = 2 → go right
    mid = 3 → count = 4 → go right
    mid = 4 → count = 4 → go right
    mid = 5 → count = 5 → go left
    Ends with low = 5 → Median = 5

This works perfectly even though the matrix is not column-sorted.

Case 1 - Even number of elements

When the total number of elements is even, you may choose floor/ceil as median. Example matrix:

[[1, 3], [2, 4]]

Case 2 - All elements same

[[7, 7], [7, 7]] → Median = 7

Case 3 - One row

[[1, 2, 3, 4, 5]] → Median = 3

Case 4 - One column

[[2], [4], [6]] → Median = 4

Case 5 - Duplicates


  [
    [1, 2, 2],
    [2, 2, 3],
    [3, 3, 4]
  ] → Median = 2

Case 6 - Large Values

[[100000, 100001], [100002, 100003]] → Median = 100001

Algorithm Steps❯

Set low = minimum element of the matrix, high = maximum element.
Perform binary search in the range [low, high]:
→ For each mid value, count how many elements are ≤ mid using upper_bound logic for each row.
→ If the count is less than or equal to (r * c) / 2, move right (low = mid + 1).
→ Else, move left (high = mid - 1).
Continue until low > high. At the end, low will be the median.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

import bisect

def matrix_median(matrix):
    r, c = len(matrix), len(matrix[0])
    low, high = matrix[0][0], matrix[0][-1]
    for row in matrix:
        low = min(low, row[0])
        high = max(high, row[-1])

    desired = (r * c) // 2
    while low <= high:
        mid = (low + high) // 2
        count = 0
        for row in matrix:
            count += bisect.bisect_right(row, mid)

        if count <= desired:
            low = mid + 1
        else:
            high = mid - 1

    return low

# Sample usage
matrix = [[1, 3, 5], [2, 6, 9], [3, 6, 9]]
print("Median is:", matrix_median(matrix))

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(r * log(max - min))	Where r is the number of rows, and binary search runs over the value range from min to max element.
Average Case	O(r * log(max - min) * log c)	Each iteration performs binary search across each row using upper_bound (O(log c)).
Worst Case	O(r * log(max - min) * log c)	Full binary search over value range with upper_bound on all rows in each step.

Space Complexity❯

O(1)

Explanation: No extra space is used beyond loop variables and counters.

⬅ Previous TopicSearch in Row and Column-wise Sorted Matrix

Next Topic ⮕Preorder Traversal of a Binary Tree using Recursion