DSA sheet · Binary Search · Search in a 2D matrix pattern

Search a Sorted Matrix

This video opens the last binary search pattern of the sheet: searching inside a 2D matrix (a grid of numbers with rows and columns). The teacher uses LeetCode 74, where the whole grid is sorted so strongly that you can run one binary search to pick the right row, and then a second binary search inside that row. The main lesson is reading the two properties of the matrix and asking "do these let me throw away half each time?". She also explains why we search the rows first and not the columns, and how that would flip if the matrix were arranged the other way.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Search a 2D Matrix: binary search on rows, then on the row
• Part B · Why rows first? The "open it up" view and the column-first twin
• Part C · Revision page

Part 0 · Before starting

Why binary search works at all

Binary search needs one thing: when you look at one position, you must be able to say for sure "the answer is not on this side". That's possible when the data is sorted (or, more generally, when some yes/no question is "no, no, no, … yes, yes, yes" in order). Then each look throws away half of what's left.

low, high, mid

• low = the first index still possible, high = the last index still possible. Together they mark the part of the array we haven't thrown away yet.
• mid = the middle of that part. We check it, then throw away the half that can't have the answer by moving low = mid + 1 or high = mid - 1.
• We stop when low > high: nothing is left to check.

Why mid = low + (high - low) // 2?

The simple form is (low + high) // 2. In Java or C++, if low and high are both close to the biggest int (about 2.1 × 10⁹), their sum overflows (goes past the biggest value and wraps around to a negative number), so mid becomes garbage. low + (high - low) // 2 never builds that big sum, so it's safe. The teacher says to choose between the two "depending on the constraints". In Python, ints never overflow, so both forms give the same answer. We still write the safe form so the habit carries over to other languages.

Matrix words used on this page

• A matrix is a grid. m × n means m rows (horizontal lines) and n columns (vertical lines).
• matrix[r][c] is the number in row r, column c. Both start at 0.
• In Python: number of rows = len(matrix), number of columns = len(matrix[0]).
• The first number of row r is matrix[r][0], the last one is matrix[r][n - 1].
• Non-decreasing means "each number is ≥ the one before it". It's "increasing, but equal neighbours are allowed".

Part A · Binary search on rows, then on the row

LeetCode 74 · Search a 2D Matrix

1The question in simple words

You get an m × n matrix of integers and a number target. Return True if target is somewhere in the matrix, otherwise False. The matrix has two special properties:

1. Every row is sorted from left to right (non-decreasing).
2. The first number of each row is bigger than the last number of the row above it.

          col 0   1   2   3
  row 0  [  1    3   5   7 ]
  row 1  [ 10   11  16  20 ]      10 > 7   (row 1 starts after row 0 ends)
  row 2  [ 23   30  34  60 ]      23 > 20  (row 2 starts after row 1 ends)

Check property 1: 1 3 5 7 sorted ✓, 10 11 16 20 sorted ✓, 23 30 34 60 sorted ✓. Check property 2: 10 > 7 ✓ and 23 > 20 ✓.

The problem also says the solution must run in O(log(m × n)). That line is a big hint, and we'll come back to it.

2What the constraints tell us

• m and n are between 1 and 100. So the matrix has at most 100 × 100 = 10⁴ numbers. At least 1 row and 1 column always exist, so matrix[0] is safe to read.
• Values and target are between −10⁴ and 10⁴: small, a normal int is fine.
• A simple linear search (look at every cell) costs m × n = 10⁴ steps. That's tiny compared to the ~10⁸ that causes TLE, so it would actually pass.
• But the question asks for O(log(m × n)). "log" in a required complexity is the problem setter telling you: use binary search. So the constraint here comes from the statement, not from the size.

3Intuition: pick the row first, then search inside it

Say the target is 3. Look at the first number of each row, the smallest number of that row:

• Row 2 starts with 23. 23 is already bigger than 3. Every number in row 2 is ≥ 23, and every row below would be even bigger. So 3 can't be in row 2 or anywhere below it.
• Row 1 starts with 10, also bigger than 3. Same reasoning: 3 is not in row 1 or below.

So one comparison against the first number of a row lets us throw away that row and everything below it. That's a "throw away a whole side" move, which is exactly binary search. But which row should we compare with first? Don't go row by row. Use binary search over the rows: check the middle row, throw away half the rows, repeat.

The goal of this first search is to find the valid row: the one row where the target would have to be, if it's in the matrix at all. It's "would" because the target might still be missing. For example, target 4 must be in row 0 if anywhere (1 ≤ 4 ≤ 7), but row 0 has no 4, so the answer is False. Still, row 0 is the only row worth searching.

Once we know the valid row, it's just a sorted 1D array, so run a normal binary search on it.

4Building the conditions from examples

First search, over rows: top = 0, bottom = rows - 1, and mid is a row number, the middle row. We compare the target with the first value matrix[mid][0] and the last value matrix[mid][n - 1] of that row.

Example target = 3 → first value bigger than target → go up

top = 0, bottom = 2 → mid = row 1, which starts at 10. 10 > 3, so 3 isn't in row 1 or below. Keep only the rows above mid:

Example target = 23 → is it "go down" or "this row"?

Mid row 1 starts at 10, and 10 < 23. The teacher's first idea was "first value smaller than target → move down". Then she stops: what if the target were 11? 10 < 11 too, but 11 is in row 1. So "first value is smaller" alone can't tell "this row" apart from "a lower row". We need to also look at the last value of the row:

• target 11: 10 ≤ 11 ≤ 20 → it fits between the first and last value of row 1 → row 1 is the valid row.
• target 23: 23 > 20 (the last value of row 1) → it's past the end of row 1 → go down.

So the teacher puts a new check before the others:

Second search, inside the valid row

Now it's a plain binary search on matrix[row]: left = 0, right = n - 1, mid is now a column number.

• matrix[row][mid] == target → return True.
• matrix[row][mid] < target → the target is to the right → left = mid + 1.
• otherwise (bigger) → the target is to the left → right = mid - 1.

If this loop ends without finding it, the valid row simply doesn't contain the target (like target 4 in row 0) → return False.

5Approach steps

1. m = len(matrix), n = len(matrix[0]).
2. Binary search over rows with top = 0, bottom = m - 1, row = -1.
3. For the mid row: if target is between its first and last value → row = mid, break. Else if target is smaller than its first value → bottom = mid - 1. Else → top = mid + 1.
4. If row == -1 → return False.
5. Binary search inside matrix[row] with left = 0, right = n - 1. Found → True.
6. Loop ended → return False.

6Code (Python)

class Solution:
    def searchMatrix(self, matrix, target):
        m = len(matrix)              # rows
        n = len(matrix[0])           # columns

        # ---- search 1: find the valid row ----
        top, bottom = 0, m - 1
        row = -1
        while top <= bottom:
            mid = top + (bottom - top) // 2
            if matrix[mid][0] <= target <= matrix[mid][n - 1]:
                row = mid            # target can only be in this row
                break
            elif target < matrix[mid][0]:
                bottom = mid - 1     # go up
            else:
                top = mid + 1        # go down

        if row == -1:                # no row can hold the target
            return False

        # ---- search 2: normal binary search inside that row ----
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                left = mid + 1       # go right
            else:
                right = mid - 1      # go left
        return False                 # valid row, but the value is missing

7Code line by line

8Dry run

Target 3 (the teacher's main example)

          col 0   1   2   3
  row 0  [  1   3   5   7 ]   ← valid row
  row 1  [ 10   11  16  20 ]   ← mid in round 1 (10 > 3, drop it and below)
  row 2  [ 23   30  34  60 ]

Now search inside row 0:

Target 23 (go down, then find)

Target 4 (valid row exists, value doesn't)

Row search: mid row 1 (10 > 4) → bottom = 0 → row 0 (1 ≤ 4 ≤ 7) → row = 0. Column search:

Target 61 (no valid row at all)

9Complexity & remember

• Time O(log m + log n) = O(log(m × n)). The first search halves the rows: log m steps. The second halves the columns of one row: log n steps. And log m + log n = log(m × n), exactly what the question asked for.
• Space O(1): just a few pointers.

Part B · Why rows first? The "open it up" view

1The question in simple words

Same problem. The teacher raises an interview-style "why": why did we binary search the rows first and the columns second? Why not columns first?

2What the constraints tell us

Same as Part A. Nothing new. This part is about understanding, not about size.

3Intuition: lay the rows out in one line

Take the rows and put them one after another (we can call this opening up the matrix, row by row):

Because each row is sorted and each row starts after the previous one ends, this line is one big sorted array of m × n = 3 × 4 = 12 numbers. Binary search on N items takes log N steps, so here it's log(m × n) = log m + log n. That sum reads like a recipe: log m work on the rows, then log n work on the columns. That's exactly Part A.

4Building the logic: which property decides the order?

Property 2 talks about rows: "a row's first value is bigger than the previous row's last value". That's what makes the row-by-row line sorted. So the rows are the "blocks" we can pick between, and we pick the row first.

Now imagine the property were about columns instead: "a column's first value is bigger than the previous column's last value". The teacher builds such a matrix:

          col 0   1   2   3
  row 0  [  1    5   8  11 ]
  row 1  [  3    6   9  12 ]
  row 2  [  4    7  10  13 ]

  read column by column: 1 3 4 | 5 6 7 | 8 9 10 | 11 12 13   sorted ✓
  (5 > 4, 8 > 7, 11 > 10: each column starts after the previous one ends)

Rows are still sorted and columns are still sorted, but now the matrix opens up into a sorted line column by column. So we flip the plan: first binary search the columns to find the valid column, then binary search down that column. The cost is log n + log m, the same total.

5Approach steps (column-first twin)

1. Binary search over columns 0 … n-1. For the mid column, compare the target with its top value matrix[0][mid] and bottom value matrix[m-1][mid].
2. Fits → that's the valid column. Smaller than the top → go left. Else → go right.
3. No valid column → False. Otherwise binary search rows 0 … m-1 inside that column.

6Code (Python)

def search_column_major(matrix, target):
    m, n = len(matrix), len(matrix[0])
    left, right = 0, n - 1
    col = -1
    while left <= right:                     # search 1: the valid column
        mid = left + (right - left) // 2
        if matrix[0][mid] <= target <= matrix[m - 1][mid]:
            col = mid
            break
        elif target < matrix[0][mid]:
            right = mid - 1
        else:
            left = mid + 1
    if col == -1:
        return False
    top, bottom = 0, m - 1
    while top <= bottom:                     # search 2: down that column
        mid = top + (bottom - top) // 2
        if matrix[mid][col] == target:
            return True
        elif matrix[mid][col] < target:
            top = mid + 1
        else:
            bottom = mid - 1
    return False

def search_flat(matrix, target):
    m, n = len(matrix), len(matrix[0])
    low, high = 0, m * n - 1
    while low <= high:
        mid = low + (high - low) // 2
        value = matrix[mid // n][mid % n]    # turn the line index into (row, col)
        if value == target:
            return True
        elif value < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

7Code line by line (what changes from Part A)

8Dry run (column-first twin, target 9)

Down column 2 = 8, 9, 10: top 0, bottom 2 → mid 1 → 9 == 9 → True.

9Complexity & remember

• Same: O(log n + log m) = O(log(m·n)) time, O(1) space.

Part C · Revision page

matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
s = Solution()
print(s.searchMatrix(matrix, 3))    # True
print(s.searchMatrix(matrix, 11))   # True
print(s.searchMatrix(matrix, 23))   # True
print(s.searchMatrix(matrix, 4))    # False  (valid row 0, value missing)
print(s.searchMatrix(matrix, 61))   # False  (no valid row)
print(s.searchMatrix([[1]], 1))     # True   (needs <= in the loops)

Based on this video: Search a 2D Matrix | Binary Search