Leetcode74. 搜索二维矩阵

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

img

1
2
>输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
>输出：true

示例 2：

img

1
2
>输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
>输出：false

用了比较傻的方法，分行二分查找，也就是在每一行都进行二分查找，最后肯定开销巨大，但是能用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        def binarySearch(arr, target):
            l,r = 0, len(arr)-1
            while l <= r:
                mid = (l + r) // 2
                if arr[mid] == target:
                    return True
                elif arr[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return True if 0 <= l <= len(arr) - 1 and arr[l] == target else False
        M,N = len(matrix), len(matrix[0])
        for i in range(M):
            if binarySearch(matrix[i],target):
                return True
        return False