大数据

lintcode第二十八题 搜索二维矩阵

lintcode的题号比较尴尬,十八题完了就直接成了二十八题,不知道是我没有找到还是它本来就是这样的。
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性:
每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。
这个数组简单的说就是从小到大依次排列,排满一行就换到下一行。
典型的二分查找,代码也很简单,只要将二维数组看成一维数组就可以了。

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
        if (matrix.size() == 0) return false;
        int m = matrix.size(),n = matrix[0].size();
        int left = 0,right = m * n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid / n][mid % n] < target) left = mid + 1;
            else right = mid;
        }
        return matrix[right / n][right % n] == target;
    }
};