Simple Python code, O(m)+O(logn)


  • 1
    J
    class Solution:
        # @param matrix, a list of lists of integers
        # @param target, an integer
        # @return a boolean
    
        '''
        Binary search of target on row
        '''
        def binarySearch(self, row, target):
        	length = len(row)
        	if length == 1:
        		if row[0] == target:
        			return True
        		else:
        			return False
    
        	mid = length // 2
        	if target == row[mid]:
        		return True
        	elif target < row[mid]:
        		return self.binarySearch(row[:mid],target)
        	else:
        		return self.binarySearch(row[mid:],target)
    
    
        def searchMatrix(self, matrix, target):
        	if len(matrix) == 0:
        		return False
    
        	for row in matrix:
        		if len(row) == 0:
        			return False
        		if target <= row[len(row)-1]:
        			return self.binarySearch(row,target)
        	return False

  • 0
    I

    Since you already use binary search on specific row to get log(n) performance, why don't you use the same technique to get log(m) performance?


Log in to reply
 

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