74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

题解1 循环分治：

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

题解2 递归分治：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int line = findLine(matrix, target, 0, matrix.length-1);
        if (line == -1)
            return false;
        else
            return check(matrix[line], target, 0, matrix[line].length-1);
    }

    public boolean check(int[] array, int target, int start, int end){
        if (array[start]==target || array[end]==target)
            return true;
        if (array[start]>target||array[end]<target)
            return false;
        int middle = (start+end)/2;
        boolean res;
        if (array[middle]<=target)
            res = check(array, target, start, middle);
        else
            res = check(array, target, middle, end);
        return res;
    }

    public int findLine(int[][] matrix, int target, int start, int end){
        if (matrix[start][0]==target)
            return start;
        if (matrix[end][0]==target)
            return end;
        if (matrix[start][0]>target||matrix[end][0]<target)
            return -1;
        int middle = (start+end)/2;
        if (matrix[middle][0]<=target && matrix[middle+1][0]>=target)
            return start;
        int res;
        if (matrix[middle][0]<=target)
            res = findLine(matrix, target, start, middle);
        else
            res = findLine(matrix, target, middle, end);
        return res;
    }
}

题解3 一次分治：

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

题解4 抽象BST：
我们可以将二维矩阵抽象成「以右上角为根的 BST」：

那么我们可以从根（右上角）开始搜索，如果当前的节点不等于目标值，可以按照树的搜索顺序进行：

当前节点「大于」目标值，搜索当前节点的「左子树」，也就是当前矩阵位置的「左方格子」，即 y—
当前节点「小于」目标值，搜索当前节点的「右子树」，也就是当前矩阵位置的「下方格子」，即 x++

class Solution {
    int m, n;
    public boolean searchMatrix(int[][] mat, int t) {
        m = mat.length; n = mat[0].length;
        int x = 0, y = n - 1;
        while (check(x, y) && mat[x][y] != t) {
            if (mat[x][y] > t) {
                y--;
            } else {
                x++;
            }
        }
        return check(x, y) && mat[x][y] == t;
    }
    boolean check(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}