careercup-排序和查找 11.6

11.6 给定M*N矩阵，每一行、每一列都按升序排序，请编写代码找出某元素。

类似leetcode：Search a 2D Matrix 但是与leetcode中这题不同的是下一行的第一个元素不一定大于上一行的最后一个元素。所以使用二分查找有点麻烦。

解法一：通过观察我们可知：

若列的开头大于x，那么x位于该列的左边；

若列的末端小于x，那么x位于该列的右边；

若行的开头小于x，那么x位于改行的上方；

若行的末端小于x，那么x位于改行的下方

我们可以从任意位置开始搜索，不过，让我们从列的起始元素开始。

我们需要从最大的那一列开始，然后向左移动，这意味着第一个要比较的元素是array[0][c-1]，其中c为列的数目。

C++实现代码：

#include<iostream>
#include<vector>
using namespace std;

bool findElememt(vector<vector<int> > &matrix,int target)
{
    if(matrix.empty()||matrix[0].empty())
        return false;
    int m=matrix.size();
    int n=matrix[0].size();
    int row=0;
    int col=n-1;
    while(row<m&&col>=0)
    {
        if(matrix[row][col]==target)
            return true;
        if(matrix[row][col]<target)
            row++;
        else
            col--;
    }
    return false;
}

int main()
{
    vector<vector<int> > vec={{15,20,40,85},{20,35,80,95},{30,55,95,105},{40,80,100,120}};
    cout<<findElememt(vec,20)<<endl;
}