Has anyone been able to come up with a fast binary search solution?


  • 2
    D
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        elif len(matrix) == len(matrix[0]) == 1:
            return matrix[0][0] == target
        r, c = len(matrix)/2, len(matrix[0])/2
    
        x = matrix[r][c]
        if x == target:
            return True
        
        elif x < target:
            return self.searchMatrix([row[c:] for row in matrix[r:]], target)\
                or self.searchMatrix([row[c:] for row in matrix[:r]], target)\
                or self.searchMatrix([row[:c] for row in matrix[r:]], target)
        else:
            return self.searchMatrix([row[:c] for row in matrix[:r]], target)\
                or self.searchMatrix([row[c:] for row in matrix[:r]], target)\
                or self.searchMatrix([row[:c] for row in matrix[r:]], target)
    

    I came up with this, which is messy and quite slow, but did barely pass OJ. Binary search is very fast in 1D arrays. Is that just not true for 2D?


  • 0
    W

    Hi,

    This is O( n^(2*log_4(3))

    https://en.wikipedia.org/wiki/Master_theorem


  • 1

    This is more like quaternary search. A binary search is possible on separate rows/columns. The simplest version in Java looks like this:

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0)
            return false;
        for (int[] row : matrix) {
            if (Arrays.binarySearch(row, target) >= 0) {
                return true;
            }
        }
        return false;
    }
    

    This is M lg N, which runs pretty fast already. For better results, pick min(M, N) and perform the linear search in along the appropriate axis, so the complexity will be then min(M, N) lg max(M, N). For even better results, use binary search on the first and last rows (or columns) to shrink the search range (because it makes no sense to perform a binary search on the first column if it ends with 5 and you're looking for 10).


  • 0
    G
    class Solution {
    public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_len = matrix.size();
        if (row_len == 0) {
            return false;
        }
        int col_len = matrix[0].size();
        
        int row = 0, col = col_len - 1;
        
        while (row < row_len && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                int row_start = row + 1, row_end = row_len - 1;
                while (row_start <= row_end) {
                    int mid = (row_start + row_end) >> 1;
                    if (matrix[mid][col] == target) {
                        return true;
                    } else if (matrix[mid][col] < target) {
                        row_start = mid + 1;
                    } else {
                        row_end = mid - 1;
                    }
                }
                if (row_end == col_len - 1) {
                    return false;
                } else {
                    row = row_end + 1;
                }
            } else {
                int col_start = 0, col_end = col - 1;
                while (col_start <= col_end) {
                    int mid = (col_start + col_end) >> 1;
                    if (matrix[row][mid] == target) {
                        return true;
                    } else if (matrix[row][mid] < target) {
                        col_start = mid + 1;
                    } else {
                        col_end = mid - 1;
                    }
                }
                if (col_end < 0) {
                    return false;
                } else {
                    col = col_end;
                }
            }
        }
        
        return false;
    }
    };
    

    I implement a binary search version, and compared to the solution:

    class Solution {
    public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        if(m==0)  return false;
        int n=matrix[0].size();
        /*** start from the right-up-position ***/
        int i=0, j=n-1;
        while(i<m && j>=0){
            if(matrix[i][j]==target)  return true;
            /*** the element-of-column-j >= matrix[i][j] > target ***/
            else if(matrix[i][j]>target)  j--;
            /*** the element-of-row-i <= matrix[i][j] < target ***/
            else   i++;
        }
        return false;
    }
    };
    

    I find that the binary search version is slower.


  • 0
    G

    @gy910210 : what is the time complexity of the above algorithm?


Log in to reply
 

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