Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Binary Search in Matrix
DSA

Binary Search in Matrix

Explore techniques for applying binary search to sorted rows, columns, and matrix representations.

Matrix search depends on how the matrix is sorted:

Fully sorted row-major → Flatten + Binary Search · Rows and columns sorted → Staircase Search

Focus on recognizing:

“Sorted matrix + find target” → pick the strategy from the sort order

When the whole matrix is one sorted sequence, treat it as a 1D array of size rows × cols:

public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;

    int lo = 0;
    int hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        int val = matrix[mid / cols][mid % cols];

        if (val == target) {
            return true;
        } else if (val < 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

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        val = matrix[mid // cols][mid % cols]

        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return False
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size(), cols = matrix[0].size();

    int lo = 0, hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        int val = matrix[mid / cols][mid % cols];

        if (val == target) return true;
        else if (val < 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;

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);

    const val = matrix[(mid / cols) | 0][mid % cols];

    if (val === target) return true;
    else if (val < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return false;
}

The trick: row = mid / cols, col = mid % cols — a virtual 1D index mapped into the grid.

Requires: last element of each row < first element of the next.

Watch the staircase hunt for 6 in a row/column-sorted grid — two eliminations down, one left. Press ▶ to animate.

Search a Sorted Matrix — Staircase (Zigzag) Walk

Search for a target in an m×n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom. Start at the top-right corner and eliminate a whole row or column each step.

Matrix [[1,4,7,11],[2,5,8,12],[3,6,9,16]]; target 6. Start top-right (11): because the column below is even bigger and the row to the left is smaller, comparing once tells you whether to drop the whole column (move left) or whole row (move down). Each step removes a full line → O(m+n).

GRID VISUALIZER
Steps –
1
4
7
11
2
5
8
12
3
6
9
16
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        r = 0, c = cols - 1      // top-right corner
                      
                        2
                        while r < m && c >= 0:
                      
                        3
                          v = matrix[r][c]
                      
                        4
                          if v == target: found
                      
                        5
                          if v > target: c--      // whole column too big → left
                      
                        6
                          else:          r++      // whole row too small → down

When only rows AND columns are sorted (not continuously), start at the top-right corner — every step eliminates a full row or column:

public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int col = matrix[0].length - 1;
    int row = 0;

    while (row < rows && col >= 0) {
        int val = matrix[row][col];

        if (val == target) {
            return true;
        } else if (val < target) {
            row++;             // left of val is even smaller → down
        } else {
            col--;             // below val is even larger → left
        }
    }

    return false;
}
def search_matrix(matrix, target):
    row, col = 0, len(matrix[0]) - 1

    while row < len(matrix) and col >= 0:
        val = matrix[row][col]

        if val == target:
            return True
        elif val < target:
            row += 1           # left of val is even smaller → down
        else:
            col -= 1           # below val is even larger → left

    return False
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int row = 0;
    int col = matrix[0].size() - 1;

    while (row < (int)matrix.size() && col >= 0) {
        int val = matrix[row][col];

        if (val == target) return true;
        else if (val < target) row++;
        else col--;
    }

    return false;
}
function searchMatrix(matrix, target) {
  let row = 0,
    col = matrix[0].length - 1;

  while (row < matrix.length && col >= 0) {
    const val = matrix[row][col];

    if (val === target) return true;
    else if (val < target) row++;
    else col--;
  }

  return false;
}

Staircase = top-right start. Smaller than target → down. Larger → left.

Common Mistakes

Flattened BS on the wrong matrix.

It needs strict row-major order (row i's last < row i+1's first). Otherwise use staircase.

Index conversion with the wrong divisor.

row = mid / cols, col = mid % cols — dividing by rows scrambles coordinates.

Staircase from the wrong corner.

Top-right works because it’s the only cell that is largest-in-row AND smallest-in-column simultaneously. Bottom-left also works; top-left/bottom-right don’t.

Reversed staircase moves.

val < target → down, val > target → left. Swapping them walks off the matrix.

Complexity

StrategyTimeSpace
FlattenedO(log(m·n))O(1)
StaircaseO(rows+cols)O(1)

My Private Notes

Notes are auto-saved locally to this device.