74 搜索二维矩阵

题目：
编写一个高效的算法来判断 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

思路：
先二分找到target所在的行，再在此行中二分查找是否存在target这个元素

代码：

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix.length == 0 || matrix[0].length == 0)
        return false;
    int row = matrix.length - 1;
    int col = matrix[0].length - 1;
    int left = 0;
    int right = row;
    while(left <= right){
        int mid = left + (right - left) / 2;
        //如果元素大于mid行的最大值，则其一定出现于大于mid的行
        if(target > matrix[mid][col])
            left = mid + 1;
        //如果元素小于mid行的最小值，则其一定出现于小于mid的行
        else if(target < matrix[mid][0])
            right = mid - 1;
        //否则，元素存在于mid行，在该行中进行二分查找
        else
            return binsearch(matrix[mid], target);
    }
    return false;
}

//此函数在数组num中查找元素target
public boolean binsearch(int[] num, int target){
    int n = num.length;
    int left = 0;
    int right = n - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(target == num[mid])
            return true;
        else if(target > num[mid])
            left = mid + 1;
        else
            right = mid - 1;
    }
    return false;
}