Search a 2D Matrix 1 - Elements sorted row-wise and first integer of each row is greater than last element of previous row is greater than last element of previous row

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:

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

C++

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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

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
    }
}

TypeScript

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.