# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
#
# Integers in each row are sorted from left to right.
# The first integer of each row is greater than the last integer of the previous row.
#
# Example 1:
#
# Input:
#
#     matrix = [
#       [1,   3,  5,  7],
#       [10, 11, 16, 20],
#       [23, 30, 34, 50]
#     ]
#     
#     target = 3
#     Output: true
#     
# Example 2:
#
# Input:
#
#     matrix = [
#       [1,   3,  5,  7],
#       [10, 11, 16, 20],
#       [23, 30, 34, 50]
#     ]
#     
# target = 13
# Output: false

# ## Thought
#
# 1. Comparing each column's head (i.e. matrix[i][0]) with the target. Then find out the row that head is <= target. Thne comparing each number with the target. 
# **Time complexity:** O(m+n)<br>
# **Space complexity:** O(1)
#
# 2. Using binary search with the first column's head (i.e. matrix[i][0]). And utilize binary search again in that row.<br>
# **Time Complexity:** O(log n)<br>
# **Space complexity:** O(m)

def searchMatrix(self, matrix, target):
    """
    :type matrix: List[List[int]]
    :type target: int
    :rtype: bool
    """
    if not matrix:
        return False
    if not matrix[0]:
        return False

    '''
    idex=0
    for i in range(len(matrix)):
        if target < matrix[i][0]:
            continue
        if target > matrix[i][0]:
            idex=i
        if target == matrix[i][0]:
            return True

    for i in range(len(matrix[idex])):
        if target == matrix[idex][i]:
            return True

    return False
    '''
    def binS(nums, target):
        head, tail = 0, len(nums)
        while head < tail:
            oldh,oldt=head,tail
            mid=(head+tail)//2
            if target < nums[mid]:
                tail=mid
            if target > nums[mid]:
                head=mid 
            if target == nums[mid]:
                return head, tail, mid                              
            if oldh==head and oldt==tail:
                break
        return head, tail, mid

    fcol=[]
    for i in range(len(matrix)):
        fcol.append(matrix[i][0])

    h,t,m=binS(fcol,target)
    h1,t1,m1=binS(matrix[m][:],target)        

    return target==matrix[m][m1]

StarcoderdataJupyterScriptsDedupFiltered