题目链接：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.

这道题的要求是在m*n的矩阵中查找指定元素target。而且矩阵中每行都有序，且每行的第一个元素均大于其前一行的最后一个元素。

思路就是一句话：把二维数组当成一个有序数组，直接二分搜索。

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

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution
{
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();
        
        int l = 0, r = m * n - 1;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(matrix[mid / n][mid % n] == target)
                return true;
            else if(matrix[mid / n][mid % n] > target)
                r = mid - 1;
            else
                l = mid + 1;
        }
        
        return false;
    }
};