写出一个高效的算法来搜索 m × n矩阵中的值。

这个矩阵具有以下特性：

每行中的整数从左到右是排序的。

每行的第一个数大于上一行的最后一个整数。

样例

考虑下列矩阵：

[

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

给出 target = 3，返回 true

挑战

O(log(n) + log(m)) 时间复杂度

标签

二分法 雅虎 矩阵

思路

采用二分查找，先二分查找target所在行，在二分查找所在列

code

class Solution {public:    /**     * @param matrix, a list of lists of integers     * @param target, an integer     * @return a boolean, indicate whether matrix contains target     */    bool searchMatrix(vector
    
     
       > &matrix, int target) {        // write your code here        int rowSize = matrix.size();        if(rowSize < 1)            return false;        int colSize = matrix[0].size();        if(target < matrix[0][0] || target > matrix[rowSize-1][colSize-1])            return false;        int rowIndex = 0, colIndex = 0;        int rowHigh = rowSize-1, rowLow = 0, rowMid = (rowHigh + rowLow) / 2;        while(rowLow <= rowHigh) {            if(matrix[rowMid][0] == target || matrix[rowMid][colSize-1] == target) {                return true;            }            else if(matrix[rowMid][0] < target && matrix[rowMid][colSize-1] > target) {                rowIndex = rowMid;                break;            }            else if(matrix[rowMid][0] > target) {                rowHigh = rowMid - 1;                rowMid = (rowHigh + rowLow) / 2;            }            else if(matrix[rowMid][colSize-1] < target){                rowLow = rowMid + 1;                rowMid = (rowHigh + rowLow) / 2;            }        }        int colHigh = colSize-1, colLow = 0, colMid = (colHigh + colLow) / 2;        while(colLow <= colHigh) {            if(matrix[rowIndex][colMid] == target) {                return true;            }            else if(matrix[rowIndex][colMid] < target) {                colLow = colMid + 1;                colMid = (colHigh + colLow) / 2;            }            else {                colHigh = colMid - 1;                colMid = (colHigh + colLow) / 2;            }        }        return false;    }};