2D binary search on both row and column indexes


  • 0
    J

    ``
    public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) return false;
    return search(matrix, 0, matrix.length, 0, matrix[0].length, target);
    }

    private boolean search(int[][] matrix, int rs, int re, int cs, int ce, int target) {
        if (rs >= re || cs >= ce) return false;
        int midx = (rs + re) / 2;
        int midy = (cs + ce) / 2;
        if (matrix[midx][midy] == target) return true;
        if (matrix[midx][midy] > target) {
            boolean found = search(matrix, rs, midx, cs, ce, target);
            return found || search(matrix, midx, midx + 1, cs, midy, target);
        } else {
            boolean found = search(matrix, midx, midx + 1, midy + 1, ce, target);
            return found || search(matrix, midx + 1, re, cs, ce, target);
        }
    }
    

    ``


Log in to reply
 

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