学步园

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.

思路：

首先对包含所需元素的行进行确认。因为是经过排序的，所以可以用二分搜索（C++有lower_bound和upper_bound两种，这里使用upper_bound）寻找到对应的行。然后对这一行再次进行二分搜索。需要的时间是O(log m + log n)。

题解：

class Solution {
public:

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        auto ubound = upper_bound(begin(matrix), end(matrix), target,
            [](const int& v1, const vector<int>& v2) -> bool
            {
                return v1 < v2[0];
            }
        );
        
        if (ubound == begin(matrix))
            return false;   // larger than the first element in first row

        ubound = prev(ubound);
        auto ubound1 = upper_bound(begin(*ubound), end(*ubound), target);
        return *prev(ubound1) == target;
    }
};