74 Search a 2D Matrix

Leetcode

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

二分法。第一次二分法，前包后不包，找到是哪一行。第二次用普通的二分法找到是哪一列，如果找不到返回 -1

 public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix==null || matrix.length==0) return false;
    int low,high,mid,t;
    low=0;
    high=matrix.length;
    while(low+1<high){
        mid=(low+high)/2;
        t=matrix[mid][0];
        if(t==target){
            return true;
        } else if (t>target){
            high=mid;
        } else {
            low=mid;
        }
    }
    int row=low;
    low=0;
    high=matrix[0].length-1;
    while(low<=high){
        mid=(low+high)/2;
        t=matrix[row][mid];
        if(t==target){
            return true;
        } else if (t>target){
            high=mid-1;
        } else {
            low=mid+1;
        }
    }
    return false;
}