[leetcode]Search a 2D Matrix

这篇博文作废，新博文地址：[leetcode]Search a 2D Matrix

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n 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.
For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.

 这道题真心不错，二分查找的运用，考察的也很直接。不罗嗦了

 public boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;//锁定target可能出现的行
        int begin = 0;
        int end = matrix.length - 1;
        boolean possibleExist = false;
        while(begin <= end){
            int mid = (begin + end)>>1;
            if(target >= matrix[mid][0] && target <= matrix[mid][matrix[mid].length - 1]){//在mid这一行
                row = mid;
                possibleExist = true;
                break;//这里一定要break，不然就死循环了，也可以设置循环条件，begin < end,这样就可以判断begin == end时候的数值了，其实差不多
            }else if(target < matrix[mid][0]){
                end = mid - 1;
            }else{
                begin = mid + 1;
            }
        }
        if(possibleExist){
            begin = 0;
            end = matrix[row].length - 1;
            while(begin <= end){
                int mid = (begin+end)>>1;
                if(target == matrix[row][mid]){
                    return true;
                }else if(target < matrix[row][mid]){
                    end = mid - 1;
                }else{
                    begin = mid + 1;
                }
            }
        }
        return false; 
    }

 其实还可以将整个2维数组给平铺开来，这样就转换成了一维数组的二分查找问题了，但是想了一下，由于一直对2维数组比较抵触，所以就没展开。