LeetCode- Search a 2D Matrix

此题主要的要点是两个方面，一个是lower_bound，一个是二分查找；lower_bound也是基于二分查找。

1. 第一列，利用二分查找法，确认target所在的列
2. 在对应的列，利用二分查找法，确认target是否存在

class Solution {
public:
    
    int lower_bound(vector<vector<int>>& matrix,int target){
        
        int start = 0;
        int end = matrix.size()-1;
        
        int mid = (start + end)/2;
        while (start <= end){
            if (target == matrix[mid][0]){
                break;
            }
            if (target < matrix[mid][0]){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
            mid = (start + end)/2;
        }
        if (end < 0)return -1;
        //mid = end;
        return mid;
        
    }
    
    bool find_mid(vector<vector<int>>& matrix, int row, int target){
        
        int start = 0;
        int end = matrix[row].size()-1;
        int mid = (start+end)/2;
        while (start <= end){
            if (matrix[row][mid] == target){
                return true;
            }
            if (target < matrix[row][mid]){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
            mid = (start+end)/2;
        }
        return false;
        
    }
    
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty())return false;
        if (target < matrix[0][0] || target > matrix[matrix.size()-1][matrix[0].size()-1])return false;
        
        int upper = 0;
        upper = lower_bound(matrix,target);
        //std::cout<<"UPPER: "<<upper<<std::endl;
        if (upper<0){
            return false;
        }
        
        return find_mid(matrix,upper,target);
        
    }
};