> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-01-2022-74.-search-a-2d-matrix.md).

# 06/01/2022 74. Search a 2D Matrix

Method: since the matrix is sorted from left to right for each row. We can use binary search to efficiently find the target value. The key is to know how to conver 2d-array to 1d array and vice versa. We can i \* n + j where n is the number of columns to convert 2d to 1d. Conversely, we can use index/n to get row index and index%n to get the column index.

Time O(log(mn)

Space O(1)

```
// Some code
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        
        //flat 2d array to 1d array i*n + j
        int left = 0;
        int right = row * col - 1;
        
        while (left <= right){
            int mid = left + (right - left)/2;
            int r = mid/col;
            int c = mid%col;
            if (matrix[r][c] == target) return true;
            if (matrix[r][c] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return false;
    }
}
```

```
// Some code
class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    // Default to first row
    int selectedRow = 0;
    // If there are multiple rows, binary search them all
    if (matrix.length > 1) {
      // Binary search the first columns vertically for the row to search
      int left = 0;
      int right = matrix.length - 1;
      while (left <= right) {
        int mid = (left + right) / 2;
        // If any of the rows start with the target, return true
        if (matrix[mid][0] == target) return true;
        // Handle the case where mid's row is now the last row of the matrix
        if (mid == matrix.length - 1) {
          selectedRow = mid;
          break;
        }
        // If we find the row, use it
        if (target > matrix[mid][0] && target < matrix[mid + 1][0]) {
          selectedRow = mid;
          break;
        }
        // Handle normal case where we need to keep searching vertically
        if (target < matrix[mid][0]) right = mid - 1; // go left
        else left = mid + 1; // go right
      }
    }
    // **********************************************************
    // Now do a regular binary search on that selected row array for that target
    // **********************************************************
    int left = 0;
    int right = matrix[selectedRow].length - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (matrix[selectedRow][mid] == target) return true;
      if (target > matrix[selectedRow][mid]) left = mid + 1; // go right
      else right = mid - 1; // go left
    }    
    // If we get here, we didn't find the target
    return false; 
  }
}
```