Matrix Binary Search

Search a 2D Matrix

考点只有一个：2D array 降维成 1D array 的 index trick.

脑残题, 题目中说了下一行的第一个一定比上一行最后一个大, 直接binarysearch.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;

        int rows = matrix.length;
        int cols = matrix[0].length;

        int left = 0;
        int right = rows * cols - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            int row = mid / cols;
            int col = mid % cols;

            if(matrix[row][col] == target){
                return true;
            } else if(matrix[row][col] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

Search a 2D Matrix II

实现的时候稍微纠结了一下收边的问题，后来一想，如果到了边上还走到越界的位置上，已经说明没有合理解了，跳出循环返回 false 就行。

这道题开始想了两种思路, 一种是search, "蛇形突破"; 另一种是将matrix中心开始划分为四个块, 但是这样实际上会漏掉一些case

[1,3,5,7]

[10,11,16,20]

[23,30,34, 50], 查找5, 这样找出来中心是11(1,1), 扫一行一列都没法找到5 错误代码

注意2D和1D互相转换,

2D转1D: row1*n+col1

1D转2D: row=index/n; col=index%n;

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 ||  matrix[0].length==0) return false;
        int m = matrix.length; int n = matrix[0].length;
        int[] idx = new int[1]; idx[0]= -1;
        search2D(matrix, 0, m*n-1, idx, target);
        if(idx[0]==-1) return false;
        int row1 = idx[0]/n; int col1 = idx[0]%n;
        System.out.println(idx[0] + " " + row1 + " " + col1);
        int[] arr = new int[row1+1];
        for(int i=0;i<=row1; i++)
            arr[i] = matrix[i][col1];

        int pos1 = Arrays.binarySearch(matrix[row1], 0, col1+1, target);
        int pos2 = Arrays.binarySearch(arr,0, row1+1, target);
        return pos1>=0 || pos2>=0;
    }

    public void search2D(int[][] matrix, int start, int end, int idx[], int target){
        if(start>end)
            return;
        int m = matrix.length; int n = matrix[0].length;

        int row1 = start/n; int col1 = start%n;
        int row2 = end/n; int col2 = end%n;
        if(matrix[row1][col1]>=target) idx[0] = row1*n+col1;
        else if(matrix[row2][col2]>=target) idx[0] = row2*n+col2;
        if(start==end) return;

        int row3 = row1+(row2-row1)/2; int col3 = col1+(col2-col1)/2;
        if(matrix[row3][col3]>=target)
            search2D(matrix, start, row3*n+col3, idx, target);
        else
            search2D(matrix, (row3+1)*n+(col3+1), end, idx, target);
    }
}

蛇形突破, 如此简单

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return false;
        int m = matrix.length; int n = matrix[0].length;

        int i = 0; int j = n-1;
        while(i<m && j>=0){
            if(matrix[i][j]<target)
                i++;
            else if(matrix[i][j]>target)
                j--;
            else
                return true;
        }
        return false;
    }
}

经paper证明, logm + logn 算法不存在

Single Element in a Sorted Array

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        return search(nums, 0, nums.length-1);
    }

    public int search(int[] nums, int start, int end){
        while(start<=end){
            int mid = start + (end-start)/2;
            if((mid==0||nums[mid-1]!=nums[mid]) && (mid==nums.length-1 || nums[mid]!=nums[mid+1]))
                return nums[mid];
            else if((mid%2==0 && nums[mid]==nums[mid+1]) || (mid%2==1 && nums[mid]==nums[mid-1]))
                start = mid+1;
            else
                end = mid-1;
        }
        return -1;
    }
}

Binary Search