二分查找, 把二维的坐标换成一维的即可。

Binary search, just convert 2D coordinate to linear coordinate.

class Solution:
    # @param matrix, a list of lists of integers
    # @param target, an integer
    # @return a boolean
    def searchMatrix(self, matrix, target):
        rowNum = len(matrix)
        colNum = len(matrix[0])
        leftI = leftJ = 0
        rightI = rowNum - 1
        rightJ = colNum - 1
        while leftI * colNum + leftJ <= rightI * colNum + rightJ:
            mid = ( leftI * colNum + leftJ + rightI * colNum + rightJ ) / 2
            midI = mid / colNum
            midJ = mid % colNum
            if matrix[midI][midJ] == target:
                return True
            elif matrix[midI][midJ] < target:
                leftI = (mid + 1) / colNum
                leftJ = (mid + 1) % colNum
            else:
                rightI = (mid - 1) / colNum
                rightJ = (mid - 1) % colNum
        return False