240. 搜索二维矩阵 II

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

解法一：

从左上开始对角线遍历，每个位置行和列分别做一次二分，即对每行每列二分，复杂度O((m+n)logn)

class Solution:
    def searchMatrix(self, matrix, target: int) -> bool:
        def binary(pos, vertical):
            start = 0
            end = len(matrix)-1 if vertical else len(matrix[0])-1
            while start <= end:
                mid = start + (end - start) // 2
                if vertical:    #搜同一列
                    if matrix[mid][pos] < target:
                        start = mid + 1
                    elif matrix[mid][pos] > target:
                        end = mid - 1
                    else:
                        return True
                else:   #搜同一行
                    if matrix[pos][mid] < target:
                        start = mid + 1
                    elif matrix[pos][mid] > target:
                        end = mid - 1
                    else:
                        return True
            return False
        #从（0，0）开始遍历对角线，注意行数和列数不一定相等（矩阵）
        for i in range(min(len(matrix), len(matrix[0]))):
            if binary(i, True) or binary(i, False):
                return True
        return False