[Leetcode]74. Search a 2D Matrix

74. Search a 2D Matrix

这道题是medium的，但是那道题第一反应就是二分法。聪明的我建了个数组，把2D的数组瞬间降低纬度变成1D，low到爆炸有木有，然后正常的二分顺利做出来，当然时间只击败了个位数个百分比。。。这是第一反应的代码。简单的题我就不讲思路了哈，直接上代码。就是这个简单的二分法，我竟然都不是一次写对的，忘了mid-1和mid+1，可耻！下不为例。不写这俩，有时候就会陷入死循环，无法让high比low小了，切记不可再犯。

public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0){
            return false;
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                list.add(matrix[i][j]);
            }
        }
        int n = list.size();
        int[] l = new int[n];
        int index = 0;
        for(int i : list){
            l[index++] = i;
        }
        return binarySearch(l, target, 0, n-1);
    }
    
    private boolean binarySearch(int[] list, int target, int low, int high){
        
        if(high < low){
            return false;
        }
        boolean result = false;
        int mid = low + (high-low)/2;
        if(list[mid] > target){
            result = binarySearch(list, target, low, mid - 1);
        }
        else if(list[mid] < target){
            result = binarySearch(list, target, mid + 1, high);
        }
        else{
            result = true;
        }
        return result;      
    }
}

当然，又更好的省去空间的办法， 直接按照2D数组搜索，而不展开，展开太傻了。不造为何，这个时间也很长，哎。这个写的时候更可耻，竟然没写小于等于，在while循环里。哎。不过也有进步，两种方法写二分这个基本点算是掌握了。这个 方法也很好，但是不是java。没有取余数和mod。这个不是二分，看了半天，不是二分，是找一个角落然后变换行列。还是咱们的办法好。那个行列方法，当做参考吧，思路还挺有意思的，不是二分，不要。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0){
            return  false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0;
        int high = m*n - 1;
        int mid = 0;
        while(low<=high){
            mid = low + (high-low)/2;
            int i = mid/n;
            int j = mid%n;
            if(target < matrix[i][j]){
                high = mid - 1;
            }
            else if(target > matrix[i][j]){
                low = mid + 1;
            }
            else{
                return true;
            }
        }
        return false;
    }
}