Search a 2D Matrix leetcode

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.

Subscribe to see which companies asked this question

首先二分查找每行的第一个元素，确定了行号后，再在当前行内进行二分查找

值得一提的是其时间复杂度为 O(log(m) + log(n)) = O(log(m*n))

bool searchMatrix(vector<vector<int>>& matrix, int target) {

    int beg = , mid, end = matrix.size()-;

    while (beg <= end)

    {

        mid = (beg + end) >> ;

        if (target < matrix[mid][])

            end = mid - ;

        else if (target > matrix[mid][])

            beg = mid + ;

        else

            return true;

    }

    int row = end;

    if (row < )

        return false;

    beg = ;

    end = matrix[row].size();

    while (beg <= end)

    {

        mid = (beg + end) >> ;

        if (target < matrix[row][mid])

            end = mid - ;

        else if (target > matrix[row][mid])

            beg = mid + ;

        else

            return true;

    }

    return false;

}

巴特西

Search a 2D Matrix leetcode

最新文章

热门文章