Search In Sorted Matrix

"Great things are done by a series of small steps brought together."

Just like searching in a matrix—progress step by step, and you'll reach your goal!

"Today we solve Search In sorted Matrix"

🔍 Search in a Sorted Matrix

Problem Statement

Given an n x m matrix where every row and every column is sorted in ascending order,

determine if a target value exists in the matrix.

Example:

Matrix:

1  4  7 11  
2  5  8 12  
3  6  9 16  
10 13 14 17
Target: 5
Output: true

1️⃣ Brute Force Approach

Algorithm:

Traverse every cell in the matrix.

If a cell matches the target, return true.

If no match is found after searching all cells, return false.

Time Complexity: O(n * m)
Space Complexity: O(1)

2️⃣ Row/Column-Wise Binary Search

Algorithm:

For each row:

Use binary search to find the target.

Stop if found, else try the next row.

Time Complexity: O(n * log m)
Space Complexity: O(1)

Staircase Search (Optimal)

Start from the top-right corner of the matrix.

At each step:

If the value equals target, return true.

If the value is greater than the target, move left (decrement column).

If the value is less than the target, move down (increment row).

Continue until you run out of matrix bounds.

Why does this work?

From the top-right, moving left guarantees smaller values (since rows are sorted), moving down guarantees larger values (since columns are sorted). Each move discards either a whole row or column, shrinking the search space efficiently.

Time Complexity: O(n + m)
Space Complexity: O(1)

🔑 Staircase Search Logic — Code in C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int n = matrix.size(), m = matrix[0].size();
    int i = 0, j = m - 1;
    while (i < n && j >= 0) {
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] > target) j--;
        else i++;
    }
    return false;
}

Java

boolean searchMatrix(int[][] matrix, int target) {
    int n = matrix.length, m = matrix.length;
    int i = 0, j = m - 1;
    while (i < n && j >= 0) {
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] > target) j--;
        else i++;
    }
    return false;
}

python

def searchMatrix(matrix, target):
    n, m = len(matrix), len(matrix)
    i, j = 0, m - 1
    while i < n and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] > target:
            j -= 1
        else:
            i += 1
    return False

Conclusion & Complexity Table

Brute Force: Checks every cell, slowest at O(n*m) time.

Row/Binary Search: Uses binary search in each row, faster at O(n*log m).

Staircase Search: Starts top-right and moves left/down, most efficient at O(n+m) time.

All methods use O(1) extra space.

Staircase Search is fastest because each step removes a whole row or column.