😮240 search a 2D matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/solution/

class Solution {
    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length-1 : matrix.length-1;

        while (hi >= lo) {
            int mid = (lo + hi)/2;
            if (vertical) { // searching a column
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else { // searching a row
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // iterate over matrix diagonals
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true;
            }
        }
        
        return false; 
    }
}

最简单直接的办法，对于每个对角线上的元素，搜索它的左边和下边，用两个binary search，时间复杂度是O(log n!)

最简单最快的办法是下面这样

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //左下角和右上角都适用
        int row = matrix.length - 1;
        int col = 0;
        
        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else {
                return true;
            }
        }
        return false;
    }
}

从左下角出发，如果大了就往上走，如果小了就往右走，时间复杂度是O(m+n)

是否可以大了往左走，小了往下走？如果是右上角是可以这样的

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //左下角和右上角都适用
        int row = 0;
        int col = matrix[0].length - 1;
        
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] < target) {
                row++;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                return true;
            }
        }
        return false;
    }
}

为什么这样能保证不漏掉呢，大的时候我们是往左上走不是往左走，但是我们不会漏掉左边的，因为我们一开始就在最左边，同理小的时候我们是往右走不是往下走，但是我们不会漏掉下面的，因为我们一开始就在最下边，所以总是可以搜索到target