I don't know why you guys like to treat this matrix as 1-D array, is that faster?


  • 0

    Well, this matrix is super ordered, and it's very easy to find the exact right row, and then we can use binary search to search that row, instead of search the whole matrix.

    Just to be clear: this solution is definitely faster than 1-D solution.

    Two binary search, beat 70% in Java, code below:

    public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            int top = 0, down = m - 1;
            // find the row
            while (top < down) {
                int mid = top + (down - top) / 2;
                if (matrix[mid][n - 1] >= target) {
                    down = mid;
                } else {
                    top = mid + 1;
                }
            }
            int row = top;
            // find the value
            int l = 0, r = n-1;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (matrix[row][mid] >= target) {
                    r = mid;
                } else if (matrix[row][mid] < target) {
                    l = mid + 1;
                }
            }
            return matrix[row][l] == target;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.