74.md

题目地址

https://leetcode-cn.com/problems/search-a-2d-matrix/

解答

class Solution:
    def searchMatrix(self, matrix: list, target: int) -> bool:
        """
            搜索二维矩阵

            编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

            每行中的整数从左到右按升序排列。
            每行的第一个整数大于前一行的最后一个整数。

            输入:
            matrix = [
              [1,   3,  5,  7],
              [10, 11, 16, 20],
              [23, 30, 34, 50]
            ]
            target = 13
            输出: false
        """
        if not matrix or not matrix[0]:
            return False
        i, j = 0, len(matrix) - 1
        k = j
        while i <= j:
            in_middle = (j + i) // 2
            if matrix[in_middle][0] == target:
                return True
            elif matrix[in_middle][0] < target:
                if in_middle == k:
                    return self.binarySearch(matrix[in_middle], target)
                if matrix[in_middle + 1][0] > target:
                    return self.binarySearch(matrix[in_middle], target)
                i = in_middle + 1
            else:
                j = in_middle - 1
        return False

    def binarySearch(self, nums, target):
        """ 二分查找 """
        i, j = 0, len(nums) - 1
        while i <= j:
            in_middle = (j + i) // 2
            if nums[in_middle] == target:
                return True
            elif nums[in_middle] < target:
                i = in_middle + 1
            else:
                j = in_middle - 1

        return False