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

  • 1
    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
        			return False
        	mid = length // 2
        	if target == row[mid]:
        		return True
        	elif target < row[mid]:
        		return self.binarySearch(row[:mid],target)
        		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

    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.