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.

思路：先从行找到合适的位置，使用二分查找，再在这一行查找目标值，也是二分查找，时间复杂度为O(lgm + lgn)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
在一个二维数组中查找一个元素 只不过这个数组是有特殊排序的
使用二分查找 
*/ 
bool Search2DMatrix(vector<vector<int> >& vec,int key)
{
    int pos;
    int low,high,mid;
    low = 0;
    high = vec.size()-1;
    while(low<=high)
    {
        mid = low+(high-low)/2;
        if(vec[mid][0] == key)
            return true;
        else if(vec[mid][0] < key)
             low= mid+1;
        else
            high = mid-1;
    }
    pos = low;   //这一块相当于使用STL中的lower_bound函数，找下界
    low = 0;
    high = vec[0].size()-1;
    while(low<=high)
    {
        mid = low+(high-low)/2;
        if(vec[pos][mid] == key)
            return true;
        else if(vec[pos][mid]>key)
            high = mid-1;
        else
            low = mid+1; 
    }
    return false;
}
int main()
{
    vector<vector<int> > vec;
    int array[]={1,3,5,7};
    int array1[]={10,11,16,20};
    int array2[]={23,30,34,50};
    vector<int> vec1(array,array+sizeof(array)/sizeof(int));
    vec.push_back(vec1);
    vector<int> vec2(array1,array1+sizeof(array1)/sizeof(int));
    vec.push_back(vec2);
    vector<int> vec3(array2,array2+sizeof(array2)/sizeof(int));
    vec.push_back(vec3);
    cout<<Search2DMatrix(vec,300);
    return 0;
}