Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has properties:

  1. Integers in each row are sorted from left to right.
  2. The first integer of each row is greater than the last integer of the previous row.

Examples

For example, consider the following matrix:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

target = 5

Output:
true

Given target = 3, return true.

Solution

Method 1 – Binary Search by Treating Matrix as a 1D Sorted Array

Intuition

Because each row is sorted and the first element of each row is greater than the last element of the previous row, the entire matrix can be viewed as a single sorted 1D array. This allows us to use classic binary search by mapping a 1D index to 2D coordinates.

Approach

  1. Treat the matrix as a 1D array of size m * n (where m is the number of rows and n is the number of columns).
  2. For a given 1D index mid, the corresponding 2D coordinates are:
    • row = mid / n
    • col = mid % n
  3. Perform binary search on the range [0, m * n - 1]:
    • If the element at (row, col) equals the target, return true.
    • If it is less than the target, search the right half.
    • If it is greater, search the left half.
  4. If the search ends, the target is not present.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n, col = mid % n;
            int val = matrix[row][col];
            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1
    for left <= right {
        mid := left + (right-left)/2
        row, col := mid/n, mid%n
        val := matrix[row][col]
        if val == target {
            return true
        } else if val < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n, col = mid % n;
            int val = matrix[row][col];
            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        val m = matrix.size
        val n = matrix[0].size
        var left = 0
        var right = m * n - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            val row = mid / n
            val col = mid % n
            val value = matrix[row][col]
            when {
                value == target -> return true
                value < target -> left = mid + 1
                else -> right = mid - 1
            }
        }
        return false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left <= right:
            mid = (left + right) // 2
            row, col = divmod(mid, n)
            val = matrix[row][col]
            if val == target:
                return True
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let (m, n) = (matrix.len(), matrix[0].len());
        let (mut left, mut right) = (0, (m * n) as i32 - 1);
        while left <= right {
            let mid = left + (right - left) / 2;
            let row = (mid / n as i32) as usize;
            let col = (mid % n as i32) as usize;
            let val = matrix[row][col];
            if val == target {
                return true;
            } else if val < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    searchMatrix(matrix: number[][], target: number): boolean {
        const m = matrix.length, n = matrix[0].length;
        let left = 0, right = m * n - 1;
        while (left <= right) {
            const mid = Math.floor(left + (right - left) / 2);
            const row = Math.floor(mid / n), col = mid % n;
            const val = matrix[row][col];
            if (val === target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(log(mn)), where m is the number of rows and n is the number of columns. Binary search is performed over the entire matrix as a flat array.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.