本文共 1795 字，大约阅读时间需要 5 分钟。

?????????m x n?????????????????????????????????????????????????????????????????????????????????????O(log m + log n)???????

?????????????????????????????????????????????????????????????????????????????????????????????????????

??????

class Solution:
    def midsearch(self, lists, target):
        left = 0
        right = len(lists) - 1
        while left <= right:
            mid = (left + right) // 2
            if lists[mid] < target:
                left = mid + 1
            elif lists[mid] == target:
                return mid
            else:
                right = mid - 1
        return -1

?????

class Solution:
    def midsearch_1(self, lists, target):
        left = 0
        right = len(lists) - 1
        while left <= right:
            mid = (left + right) // 2
            if target < lists[mid][0]:
                right = mid - 1
            elif target > lists[mid][0]:
                left = mid + 1
            else:
                return mid
        return -1

???

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix:
            return False
        rows = [row[0] for row in matrix]
        j = self.midsearch_1(rows, target)
        if j == -1:
            if target > matrix[-1][-1]:
                return False
            else:
                row = matrix[-1]
                i = self.midsearch(row, target)
                return i != -1
        else:
            row = matrix[j]
            i = self.midsearch(row, target)
            return i != -1

????

????????????????????????????????O(log m + log n)????????