边工作边刷题：70天一遍leetcode: day 61-5

Search a 2D Matrix II

要点：不讨论O(n)算法，O(lgn)的算法可以用四分法，每次可以去掉2个象限，如何想是哪两个？按照递增的顺序，如图。注意这题的binary search部分不是search>target或者>=target, 而是普通的binary search，只是在没有找到的情况，利用了low在>的位置的特性。下面是一些其他细节：

• 因为是row-major，所以>的那一行要包括
• 边界条件：任何row或者column方向坐标low/high过界，如果都没过界，即使是一条线，也可以用binary search来找

错误点：

• 注意top在坐标上是小于down的

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        def search(matrix, l, r, t, d, target):
            if l>r or t>d:
                return False
            
            m = t + (d-t)/2
            low,high = l,r
            while low<=high:
                mid = low + (high-low)/2
                if matrix[m][mid]==target:
                    return True
                if matrix[m][mid]>target:
                    high = mid-1
                else:
                    low = mid+1
            
            return search(matrix, l, low-1, m+1, d, target) or search(matrix, low, r, t, m-1, target) 
        
        m = len(matrix)
        if m==0: return False
        n = len(matrix[0])
        return search(matrix, 0, n-1, 0, m-1, target)