What is the complexity of this solution? Binary search on four edges. My answer is in average log(m)*log(m), assuming m > n; worst case m*log(m)


  • 0
    L
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix.length == 0 || matrix[0].length == 0) return false;
            return helpSearch(matrix, target, 0, 0, matrix.length-1, matrix[0].length-1);
        }
        private boolean helpSearch(int[][] matrix, int target, int r1, int c1, int r2, int c2) {
            if (r1 > r2 || c1 > c2) return false;
            if (r1 == r2 && c1 == c2) return matrix[r1][c1] == target;
            int l = r1;
            int r = r2;
            while (l < r) {
                int mid = (l+r+1)/2;
                if (matrix[mid][c1] == target) return true;
                if (matrix[mid][c1] < target) l = mid;
                else r = mid-1;
            }
            r2 = r;
            
            l = c1;
            r = c2;
            while (l < r) {
                int mid = (l+r+1)/2;
                if (matrix[r1][mid] == target) return true;
                if (matrix[r1][mid] < target) l = mid;
                else r = mid-1;
            }
            c2 = r;
            
            l = r1;
            r = r2;
            while (l < r) {
                int mid = (l+r)/2;
                if (matrix[mid][c2] == target) return true;
                if (matrix[mid][c2] < target) l = mid+1;
                else r = mid;
            }
            r1 = l;
            
            l = c1;
            r = c2;
            while (l < r) {
                int mid = (l+r)/2;
                if (matrix[r2][mid] == target) return true;
                if (matrix[r2][mid] < target) l = mid+1;
                else r = mid;
            }
            c1 = l;
            return helpSearch(matrix, target, r1, c1, r2, c2);
        }
    

Log in to reply
 

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