题目描述：

 

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:matrix = [  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]target = 3输出: true

示例 2:

输入:matrix = [  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]target = 13输出: false

 

要完成的函数：

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

 

说明：

1、这道题给定一个m行n列的矩阵，要求编写一个高效的算法来判断矩阵中是否含有target这个元素。

如果存在，返回true，否则返回false。

2、这道题其实就是二分法在矩阵上的应用，整个矩阵是升序的。

我们先用二分法确定target可能会在哪一行，接着再用二分法确定target在哪一列，或者不存在。

代码如下：（附详解）

bool searchMatrix(vector
     
      
       >& matrix, int target)     {        if(matrix.size()==0||matrix[0].size()==0)return false;//[]或者[[]]的边界条件        int hang=matrix.size(),lie=matrix[0].size(),left=0,right=hang-1,med,t;        while(left<=right)//二分法判断target在哪一行        {            med=(left+right)/2;            if(target
       
        matrix[med][lie-1])                left=med+1;            else//找到元素在med这一行了            {                t=med;                left=0;                right=lie-1;                while(left<=right)//用二分法找到target在哪一列                {                    med=(left+right)/2;                    if(matrix[t][med]==target)//找到了返回true                        return true;                    else if(target
       
      
     

上述代码实测8ms，beats 97.83% of cpp submissions。