search_in_matrix.py

class Solution:
    # @param matrix, a list of lists of integers
    # @param target, an integer
    # @return a boolean
    def searchMatrix(self, matrix, target):
        if not matrix or len(matrix) == 0:
            return False

        # Flatten the matrix into 1D array, complexity is O(K).
        # K means the length of the new array.
        array = []
        for line in matrix:
            array.extend(line)

        return self.binary_search(array, target)
    
    def binary_search(self, array, target):
        start = 0
        end = len(array) - 1

        while start+1 < end:
            mid = start + (end-start)/2

            if array[mid] > target:
                end = mid
            elif array[mid] < target:
                start = mid
            else: # found the target
                return True

        if array[start] == target or array[end] == target:
            return True

        return False