a simple python solution - O(logn)


  • 0
    R

    '''
    def searchMatrix(self, matrix, target):
    if not matrix or not matrix[0]: return False
    row_s = 0
    row_e = len(matrix) - 1
    col_s = 0
    col_e = len(matrix[0]) - 1

        mid_row = row_s + (row_e - row_s)/2
        while row_s <= row_e:
            if matrix[mid_row][0] > target:
                row_e = mid_row - 1
                
            elif matrix[mid_row][-1] < target:
                row_s = mid_row + 1
            else:
                break
            mid_row = row_s + (row_e - row_s)/2
            
        mid_col = col_s + (col_e - col_s)/2
        while col_s <= col_e:
            if matrix[mid_row][mid_col] == target:
                return True
            elif matrix[mid_row][mid_col] > target:
                col_e = mid_col - 1
            else:
                col_s = mid_col + 1
            mid_col = col_s + (col_e - col_s)/2
        return False
    

    '''


Log in to reply
 

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