<reponame>kadaliao/leetcode
#
# @lc app=leetcode.cn id=74 lang=python3
#
# [74] 搜索二维矩阵
#
# https://leetcode-cn.com/problems/search-a-2d-matrix/description/
#
# algorithms
# Medium (41.15%)
# Total Accepted:    91.5K
# Total Submissions: 220.7K
# Testcase Example:  '[[1,3,5,7],[10,11,16,20],[23,30,34,60]]\n3'
#
# 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
#
#
# 每行中的整数从左到右按升序排列。
# 每行的第一个整数大于前一行的最后一个整数。
#
#
#
#
# 示例 1：
#
#
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# 输出：true
#
#
# 示例 2：
#
#
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
# 输出：false
#
#
#
#
# 提示：
#
#
# m == matrix.length
# n == matrix[i].length
# 1
# -10^4
#
#
#
from typing import List


class Solution:
    def searchMatrix0(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        l, r = 0, m * n - 1
        while l <= r:
            mid = (l + r) // 2
            i, j = divmod(mid, n)
            if target < matrix[i][j]:
                r = mid - 1
            elif target > matrix[i][j]:
                l = mid + 1
            else:
                return True
        return False

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        l, r = 0, m - 1
        while l <= r:
            mid = (l + r) // 2
            if target < matrix[mid][0]:
                r = mid - 1
            elif target > matrix[mid][-1]:
                l = mid + 1
            else:
                # 二分的跳出，以l<=r为条件，mid就是最终结果
                break
        row = mid
        l, r = 0, n - 1
        while l <= r:
            mid = (l + r) // 2
            if target < matrix[row][mid]:
                r = mid - 1
            elif target > matrix[row][mid]:
                l = mid + 1
            else:
                return True
        return False


# matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
# matrix = [[1]]
# target = 1

# ret = Solution().searchMatrix(matrix, target)
# print(ret)

#
# @lc app=leetcode.cn id=74 lang=python3
#
# [74] 搜索二维矩阵
#
# https://leetcode-cn.com/problems/search-a-2d-matrix/description/
#
# algorithms
# Medium (41.15%)
# Total Accepted:    91.5K
# Total Submissions: 220.7K
# Testcase Example:  '[[1,3,5,7],[10,11,16,20],[23,30,34,60]]\n3'
#
# 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
#
#
# 每行中的整数从左到右按升序排列。
# 每行的第一个整数大于前一行的最后一个整数。
#
#
#
#
# 示例 1：
#
#
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# 输出：true
#
#
# 示例 2：
#
#
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
# 输出：false
#
#
#
#
# 提示：
#
#
# m == matrix.length
# n == matrix[i].length
# 1
# -10^4
#
#
#
from typing import List


class Solution:
    def searchMatrix0(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        l, r = 0, m * n - 1
        while l <= r:
            mid = (l + r) // 2
            i, j = divmod(mid, n)
            if target < matrix[i][j]:
                r = mid - 1
            elif target > matrix[i][j]:
                l = mid + 1
            else:
                return True
        return False

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        l, r = 0, m - 1
        while l <= r:
            mid = (l + r) // 2
            if target < matrix[mid][0]:
                r = mid - 1
            elif target > matrix[mid][-1]:
                l = mid + 1
            else:
                # 二分的跳出，以l<=r为条件，mid就是最终结果
                break
        row = mid
        l, r = 0, n - 1
        while l <= r:
            mid = (l + r) // 2
            if target < matrix[row][mid]:
                r = mid - 1
            elif target > matrix[row][mid]:
                l = mid + 1
            else:
                return True
        return False


# matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
# matrix = [[1]]
# target = 1

# ret = Solution().searchMatrix(matrix, target)
# print(ret)
# # @lc app=leetcode.cn id=74 lang=python3 # # [74] 搜索二维矩阵 # # https://leetcode-cn.com/problems/search-a-2d-matrix/description/ # # algorithms # Medium (41.15%) # Total Accepted:    91.5K # Total Submissions: 220.7K # Testcase Example:  '[[1,3,5,7],[10,11,16,20],[23,30,34,60]]\n3' # # 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： # # # 每行中的整数从左到右按升序排列。 # 每行的第一个整数大于前一行的最后一个整数。 # # # # # 示例 1： # # # 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 # 输出：true # # # 示例 2： # # # 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 # 输出：false # # # # # 提示： # # # m == matrix.length # n == matrix[i].length # 1 # -10^4 # # # # 二分的跳出，以l<=r为条件，mid就是最终结果 # matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] # matrix = [[1]] # target = 1 # ret = Solution().searchMatrix(matrix, target) # print(ret)