A Python binary search solution - O(logn)

  • 16

    It is basically an advanced version of the binary search

    class Solution:
        # @param matrix, a list of lists of integers
        # @param target, an integer
        # @return a boolean
        # 8:21
        def searchMatrix(self, matrix, target):
            if not matrix or target is None:
                return False
            rows, cols = len(matrix), len(matrix[0])
            low, high = 0, rows * cols - 1
            while low <= high:
                mid = (low + high) / 2
                num = matrix[mid / cols][mid % cols]
                if num == target:
                    return True
                elif num < target:
                    low = mid + 1
                    high = mid - 1
            return False

  • 1

    This is brilliant !!

  • 8

    Strictly, I think this is O(logmn)

  • 2

    Another solution. small difference in checking boundary

    class Solution(object):
        def searchMatrix(self, matrix, target):
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            if not matrix or not matrix[0]:
                return False
            l, r = 0, len(matrix)*len(matrix[0])
            while l<r:
                mid = (l+r)//2
                i, j = mid//len(matrix[0]), mid%len(matrix[0])
                if matrix[i][j]==target:
                    return True
                elif matrix[i][j]>target:
                    r = mid
                    l = mid + 1
            return False

  • 0
    This post is deleted!

  • 1

    gj.And here is my solution, beat 100% and I think it is easy to understand

    if not matrix or not matrix[0]: return False
            for i in range(len(matrix)):
                if target==matrix[i][-1]: return True
                elif target<matrix[i][-1]:
                    for j in range(len(matrix[0])):
                        if matrix[i][j]==target: return True
                    return False
            return False

Log in to reply

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