"""
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
 

示例 1：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
输出：true
示例 2：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出：false
示例 3：

输入：matrix = [], target = 0
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"""

from typing import *

class Solution:
    def locateRow(self, matrix, target):
        from_i, to_i = 0, len(matrix)-1
        while from_i < to_i:
            mid = (from_i + to_i) // 2
            if matrix[mid][0] > target:
                to_i = mid - 1
            elif from_i == mid:
                if matrix[to_i][0] <= target:
                    return to_i
                else:
                    return from_i
            else:
                from_i = mid
        return from_i

    def locateCol(self, matrix, row, target):
        from_j, to_j = 0, len(matrix[row])-1
        while from_j <= to_j:
            mid = (from_j + to_j) // 2
            if matrix[row][mid] == target:
                return mid
            elif matrix[row][mid] < target:
                from_j = mid + 1
            else:
                to_j = mid - 1
        return -1

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        row = self.locateRow(matrix, target)
        col = self.locateCol(matrix, row, target)
        return col != -1


if __name__ == '__main__':
    s = Solution()
    print(s.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,50]], 50))