# Leetcode 0074 Search 2d Matix

## Problem Statement

• Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

### Example

``````
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

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

``````

## Solution Approaches

### O(N * Log(M)) Binary Search Row Wise

• As rows are sorted perform Binary Search Algorithm on each
• If `target` is not found at the end of search then move to the next row
• Time for binary search is `log M` which is applied on `N rows` so `O(N * Log(M))` in total.

### O(Log(N * M)) sO(1) Binary Search Entire

• First Element of each row is greated than last element of previous
• By the above property we can simply vizualize the this 2D matrix to be sorted 1D matrix
• If we can associate approriate indexes of that 1D matix to 2D then we this problem simplies to a plain Binary Search Algorithm
• Indexes of 1D matrix are of formed by `mat2D[i][j] = mat1D[i*(n) + j]`
``````
| (i,j) | 0     | 1     | 3     | 3     | 4     |
| ----- | ----- | ----- | ----- | ----- | ----- |
| 0     | (0,0) | (0,1) | (0,2) | (0,3) | (0,4) |
| 1     | (1,0) | (1,1) | (1,2) | (1,3) | (1,4) |
| 2     | (2,0) | (2,1) | (2,2) | (2,3) | (2,4) |
| 3     | (3,0) | (3,1) | (3,2) | (3,3) | (3,4) |

| (n * i + j) | 0   | 1   | 3   | 3   | 4   |
| ----------- | --- | --- | --- | --- | --- |
| 0           | 0   | 1   | 2   | 3   | 4   |
| 1           | 5   | 6   | 7   | 8   | 9   |
| 2           | 10  | 11  | 12  | 13  | 14  |
| 3           | 15  | 16  | 17  | 18  | 19  |

``````
``````

int getval(vector<vector<int>> &matrix, int mid){
int n = (matrix[0].size());
return matrix[mid/n][mid%n];
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int low = 0;
int high = matrix.size() * matrix[0].size() - 1 ;

while (low <= high) {
int mid = (low + high) / 2;
int midval = getval(matrix, mid);
if (midval == target) {return true;}
else if (midval < target) {
low = mid + 1;
}
else {
high = mid-1;
}
}
return false;

}

``````