题目

难度：★★★☆☆
类型：二维数组
方法：二分法

传送门

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

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

示例

示例 1

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

示例 2

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false

解答

考虑到将矩阵排列成一个一维数组后，是有序的，因此可以看做是一个排序数组中的元素寻找的问题，可以用二分法解决。

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix:
            return False
        r, c = len(matrix), len(matrix[0])
        get_value = lambda i: matrix[i // c][i % c]

        left, right = 0, r * c - 1
        while left <= right:
            middle = left + (right - left) // 2
            if get_value(middle) == target:
                return True
            elif get_value(middle) < target:
                left = middle + 1
            else:
                right = middle - 1
        return False

如有疑问或建议，欢迎评论区留言~