#!/usr/bin/env python3

__author__ = 'Wei Mu'

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        if target < matrix[0][0] or target > matrix[-1][-1]:
            return False
        
        for i in range(len(matrix)):
            if target >= matrix[i][0] and target <= matrix[i][-1]:
                row = i
                break
            elif target < matrix[i][0] and target > matrix[i-1][0]:
                return False
        
        
        
        start = 0
        end = len(matrix[row])-1
        mid = (start + end) // 2
        
        if matrix[row][start] == target or matrix[row][end] == target:
            return True
        
        while end - start != 1:
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] > target:
                end = mid
                mid = (start + end) // 2
            else:
                start = mid
                mid = (start + end) // 2
        
        return False
