Search a 2D Matrix

Problem Statement

In this problem, you are provided with a matrix that adheres to two specific properties: each row within the matrix is sorted in non-decreasing order, and the first element of each subsequent row is always greater than the last element of the previous row. Given such a structured matrix, you are tasked with determining if a specified integer (referred to as target) exists within this matrix. The challenge is to implement this search functionality with a time complexity of O(log(m * n)), where m is the number of rows and n is the number of columns in the matrix. This implies the need for an algorithm that is more efficient than a straightforward linear search, leveraging the ordered nature of the matrix to achieve logarithmic time complexity.

Examples

Example 1

Input:

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:

true

Example 2

Input:

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Output:

false

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Approach and Intuition

The structured nature of the matrix allows us to employ a search technique that takes advantage of both the sorted rows and the ordered inter-row transition. This can intuitively lead us to a binary search strategy, not just over rows or columns individually, but over the matrix as a whole. Here's the guiding logic:

1. Treat the matrix as if it were a single sorted array. Given the properties of the matrix, we can map a 2D index pair (i, j) to a single index in a hypothetical 1D array version of this matrix.
2. Start with binary search:
   • Calculate the middle index of this conceptual 1D array.
   • Convert this 1D index back to a 2D index pair (i, j). Determine i by dividing the index by the number of columns. Find j by taking the index modulo the number of columns.
   • Compare the element at matrix[i][j] with the target:
     • If they match, return true.
     • If the matrix element is larger than the target, move the search to the left half.
     • Otherwise, move to the right half.
3. If we exhaust the search space and haven't found the target, return false.

This approach ensures that each step of the search cuts the search space in half, resulting in a logarithmic time complexity relative to the total number of elements in the matrix, hence achieving the desired O(log(m * n)) performance.

Solutions

class Solution {
  public:
  bool findInMatrix(vector<vector<int>>& grid, int value) {
    int rows = grid.size();
    if (rows == 0)
        return false;
    
    int cols = grid[0].size();
    int start = 0, end = rows * cols - 1;
    int midIndex, midValue;
    while (start <= end) {
      midIndex = (start + end) / 2;
      midValue = grid[midIndex / cols][midIndex % cols];
      if (value == midValue)
          return true;
      else {
        if (value < midValue)
            end = midIndex - 1;
        else
            start = midIndex + 1;
      }
    }
    return false;
  }
};