Matrix Binary Search

Search a 2D Matrix

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

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 就行。

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 x = rows - 1;
        int y = 0;

        while(x >= 0 && y < cols){
            int cur = matrix[x][y];
            if(cur == target){
                return true;
            } else if(cur < target){
                y ++;
            } else {
                x --;
            }
        }

        return false;
    }
}