240.搜索二维矩阵II

解题思路

看到两个关键词，有序+寻找目标值，很自然的想到二分查找。

当二维数组中的某一行首元素<=target，并且尾元素>=target 时，那么target可能在这一行。

因此，首先寻找所有可能有target的行，保存在数组中。

接下来对这些行，进行二分查找，找到就返回true，没找到就对下一个符合条件的行进行二分查找。

假如最后都没有找到target，那就是matrix二维数组中不存在target，返回false。

class Solution {
    
public:
    bool b_search(const vector<int>& vec,int target)
    {
    
        int left=0,right=vec.size()-1;
        int mid;
        while(left<=right)
        {
    
            mid=left+(right-left)/2;
            if(vec[mid]==target)
                return true;
            else if(vec[mid]<target)
                left=mid+1;
            else
                right=mid-1;   
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
        int m=matrix.size(),n=matrix[0].size();
        vector<int>search_row;
        for(int i=0;i<m;++i)
        {
    
            int first_num=matrix[i][0];
            int last_num=matrix[i][n-1];
            if(target==first_num||target==last_num) return true;
            if(target>first_num&&target<last_num)
                search_row.push_back(i);
        }

        for(auto& row:search_row)
        {
    
            if(b_search(matrix[row],target))
                return true;
        }

        return false;
    }
};