题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例一

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例二：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length

n == matrix[i].length

1 <= n, m <= 300

-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9

思路：

思路一：
暴力解法，直接两层循环遍历，可行原因，m,n较小，O(mn)的时间复杂度并不大。

思路二：
对每行进行遍历，采用二分法进行行遍历（行有序），注意遍历前可以特判，若行首比目标还大，说明此后的所有行都会比目标值大，结束遍历返回false，若行尾比目标值还小说明当前行肯定都比目标小，不需要遍历改行，直接contine,若特殊情况都不满足，则对改行进行二分查找。

思路三：
巧妙的从右上角进行遍历，若当前值大，则往左移动一位，若当前值小，则往下移动一位。

代码

思路一

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==target:
                    return True
        return False

思路二

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def serachdata(matrixline:List[int],target:int) -> bool:
            n = len(matrixline)
            l = 0
            r = n-1

            while(l<=r):
                mid = (l+r)//2
                if(matrixline[mid]>target):
                    r =mid-1
                elif matrixline[mid]<target:
                    l = mid+1
                elif matrixline[mid]==target:
                    return True
            return False
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            if(matrix[i][-1]<target):
                continue
            if matrix[i][0]>target:
                break
            if serachdata(matrix[i],target):
                return True
        return False

思路三

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        i = 0
        j = n-1
        while(i<m and j>=0):
            if matrix[i][j]==target:
                return True
            elif matrix[i][j]>target:
                j -=1
            else: i+=1
        return False