## Thursday, November 13, 2014

### [LeetCode] Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n 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.
For example,
Consider the following matrix:
```[
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
```
Given target = `3`, return `true`.

1. 左边界：A[i,0]为row i  ~ row m-1的最小值。

2. 右边界：A[i, n-1]为row 0 ~ row i的最大值。

3. 上边界：A[0, j]为col j ~ col n-1的最小值。

4. 下边界：A[m-1, j]为col 0 ~ col j的最大值。

1，4组合对应左下角：target < A[i, j]时，向上搜索；反之向右搜索
2，3组合对应右上角：target < A[i, j]时，向左搜索；反之向下搜索

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

#### 1 comment:

1. Hm.. this algorithm will take O(Max(m,n)) time compare to using binary search, which takes O(lg(mn)) time. From the question we can know all elements are strictly sorted based on 1D index, so just search from left = 0, right = m * n - 1 and using matrix[mid/colNum][mid%colNum] to convert 1D index to 2D.