[LC 240]. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

从top right corner开始,如果 target 就向左移一列。

从2D的角度,也是一种binary search

好好想算法就能很简单的一道题

有趣的是,[LC 74]. Search a 2D Matrix也可以用一摸一样的code解决,虽然这道题有多种不同的解法,例如treat 2D array as 1D.

以下是这段通用的code

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0, j = cols - 1;
        while (i < rows && j >= 0) {
             if (matrix[i][j] == target) return true;
             else if (matrix[i][j] < target) {
                 i++;
             } else {
                 j--;
             }
        }
        
        return false;
    }

对74,另外一种1D的做法(要点:a[i] -> A[i/cols][i%cols])

    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, j = m * n - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (matrix[mid / n][mid % n] < target) {
                i = mid + 1;
            } else if (matrix[mid / n][mid % n] > target) {
                j = mid - 1;
            } else {
                return true;
            }
        }
        return false;
 
    }