LeetCode-74. 搜索二维矩阵

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

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

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int j = matrix.size();
        for(int i = 0; i < j; i++){
            int k = matrix[i].size();
            if(k == 0) continue;
            if(matrix[i][k-1] == target) return true;
            else if(matrix[i][k-1] < target) continue;
            return hasNumInArray(matrix[i], target);
        }
        return false;
    }
    bool hasNumInArray(vector<int> &a, int num){
        int i = 0, j = a.size();
        while(i < j){
            int mid = (i + j)/2;
            if(a[mid] == num) return true;
            else if(num > a[mid]){
                i = mid+1;
            }else{
                j = mid;
            }
        }
        return false;
        
    }
};

首先检查每一行的最后一个元素。如果等于直接返回，如果小于目标值，说明不在该行，继续进行下一行的检查。当上一行的最后一个元素比目标值大，当前行最后一个元素比目标值小时，就只在该行进行搜索（二分）。如果能够搜索到则返回true，找不到则说明整个矩阵内没有目标值。

待优化的点：在进行对每一列的检查时，也可以使用二分来加速范围的选择。

Solution1：