• 分类：BinarySearch

• 考察知识点：BinarySearch

• 最优解时间复杂度：O(log(n+m))原版/O(logn)改进版

• 最优解空间复杂度：O(1)

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

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

Example 2:

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

代码：

BinarySearch方法1:

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix)==0 or len(matrix[0])==0 or matrix[0][0]>target or matrix[-1][-1]<target:
            return False

        list_new=[]
        for each in matrix:
            list_new+=each
        start=0
        end=len(list_new)-1
        while end-start>1:
            mid=(end-start)//2+start
            if target==list_new[mid]:
                return True
            elif target<list_new[mid]:
                end=mid
            else:
                start=mid

        if list_new[start]==target:
            return True
        if list_new[end]==target:
            return True
        return False

BinarySearch方法2改进版:

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix)==0 or len(matrix[0])==0 or matrix[0][0]>target or matrix[-1][-1]<target:
            return False

        row=len(matrix)-1
        while(matrix[row][0]>target):
            row-=1

        start=0
        end=len(matrix[row])-1
        while(end-start)>1:
            mid=(end-start)//2+start
            if matrix[row][mid]==target:
                return True
            elif matrix[row][mid]<target:
                start=mid
            else:
                end=mid
        if matrix[row][start]==target or matrix[row][end]==target:
            return True

        return False

讨论：

1.排序的，然后找数字，一看到这两个条件，那么肯定是用binary search!切记切记
2.改进的方法先判断每一行是否是比原来的大，然后再每一小行做BinarySearch就可以了

我真牛逼啊哈哈！