Question 36 : Search in a row wise and column wise sorted matrix.

Given row wise and column wise sorted matrix ,we need to search element with minimum time complexity.

Example

matrix =

[

  [10, 20, 30, 40],

  [15, 25, 35, 45],

  [27, 29, 37, 48],

  [32, 33, 39, 50]

]

target = 29

Return = true

Java — Staircase Search

public class MatrixSearch {

    public static boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        if (n == 0) return false;
        int m = matrix[0].length;

        int row = 0, col = m - 1;

        while (row < n && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
}

Python:

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    n = len(matrix)
    m = len(matrix[0])
    row, col = 0, m - 1

    while row < n and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1

    return False

Alternative — Binary Search per Row
import java.util.Arrays;

public class MatrixSearchBinary {

    public static boolean search(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = Arrays.binarySearch(row, target);
            if (index >= 0) return true;
        }
        return false;
    }
}
Python 
import bisect

def search_matrix_binary(matrix, target):
    for row in matrix:
        i = bisect.bisect_left(row, target)
        if i < len(row) and row[i] == target:
            return True
    return False




  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      Staircase search (top-right)
    
    

      O(n + m)
    
    

      O(1)
    
    

      ⭐ Best & optimal
    
  

  

    

      Binary search each row
    
    

      O(n log m)
    
    

      O(1)
    
    

      ✔ Uses sorted rows
    
  

  

    

      Brute force scan all
    
    

      O(n × m)
    
    

      O(1)
    
    

      ❌ Slow for large grids