编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

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

示例 2：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10⁴ <= matrix[i][j], target <= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解1 2021/9/10 O(mxn)

def searchMatrix(matrix: list, target: int) -> bool:
    # 题目限定了matrix非空
    if matrix[0][0]>target or matrix[-1][-1]<target: return False
    m=matrix.__len__()
    n=matrix[0].__len__()
    i=0
    # 跳到行首比target大的地方，直到最末一行
    while i<m-1 and matrix[i+1][0]<=target:
        i+=1
    return target in matrix[i]

if __name__ == '__main__':
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]; target = 3
    print(searchMatrix(matrix,target))
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]; target = 13
    print(searchMatrix(matrix, target))
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]; target = 23
    print(searchMatrix(matrix, target))
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]; target = 16
    print(searchMatrix(matrix, target))
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]; target = 15
    print(searchMatrix(matrix, target))
    matrix = [[1, 3, 5, 7]]; target = 15
    print(searchMatrix(matrix, target))
    matrix = [[99, 103]]; target = 15
    print(searchMatrix(matrix, target))
    matrix = [[99],[103]]; target = 103
    print(searchMatrix(matrix, target))