第三类

在二维上运用binary search

• Search a 2d Matrix
• Search a 2d Matrix II

Search a 2D Matrix

2d matrix的二维二分查找，其实可以将二维的坐标变为一维，就又变成了普通的二分查找

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = len(matrix)
        col = len(matrix[0])

        start, end = 0, col * row - 1

        while start + 1 < end:
            mid = start + (end - start) / 2
            x = mid / col
            y = mid % col
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] > target:
                end = mid
            else:
                start = mid

        startX = start / col
        startY = start % col
        if matrix[startX][startY] == target:
            return True
        endX = end / col
        endY = end % col
        if matrix[endX][endY] == target:
            return True

        return False

Search a 2D Matrix II

这个matrix的排序比较特别，是从左到右递增，从上到下递增 可以从第一行的最右边开始查找，如果大于可以排除左边的，如果小于可以排除下面的

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = len(matrix)
        col = len(matrix[0])

        x = 0
        y = col - 1
        while x < row and y >= 0:
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] > target:
                y -= 1
            else:
                x += 1

        return False