NeetCode 150 [Binary Search]:medium 1/5

NeetCodeのSolutionを書いていく

Search a 2D Matrix

問題概要

m x n の2次元配列matrixと整数targetが与えられます。
それぞれの行は昇順で並べられています。
すべての行の最初の整数が前の行の最後の整数より大きいです。
targetがあればTrueをなければFalseを返しなさい。

例

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10
Output: true

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15
Output: false

制約

• m は matrix.length
• n は matrix[i].length
• m,n は 1以上100以下
• matrix[i][j], target は -10000以上10000以下

計算時間：O(log(m * n))
メモリ：O(1)

メモ

ソート済みなので、targetが含まれていそうなrowをバイナリサーチで探す≒O(logm)、見つけたrowからtargetを探す≒O(logn)でO(logm*n)?

from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 行を2分探索で探す
        low, high = 0, len(matrix) - 1
        while low <= high:
            r = (low + high) // 2
            min_val = matrix[r][0]
            max_val = matrix[r][-1]
            if min_val <= target <= max_val:
                break
            elif target < min_val:
                high = r - 1
            else:
                low = r + 1
        else:
            return False  # 行が見つからなかった

        # 列を2分探索で探す
        row = matrix[r]
        low, high = 0, len(row) - 1
        while low <= high:
            c = (low + high) // 2
            v = row[c]
            if v == target:
                return True
            elif target < v:
                high = c - 1
            else:
                low = c + 1
        return False