💨

NeetCode 150 [Binary Search]:easy

2025/01/21に公開

NeetCodeのSolutionを書いていく

昇順に並べられた整数のリストと、ターゲットの整数を与えられる。
リストに含まれるターゲットを見つけ、ある場合はそのインデックスを、ない場合は-1を返す関数を作る。

O(logn)時間で解決できる必要がある。

ソート済みだから2分探索すればいいのかな?

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        def search_inner(nums: list[int], target: int) -> int:
            num = nums[len(nums) // 2]

            if num == target:
                return True

            if len(nums) == 1:
                return False

            if target < num:
                return search_inner(nums[: len(nums) // 2], target)
            return search_inner(nums[len(nums) // 2 :], target)

        return nums.index(target) if search_inner(nums, target) else -1

戻り値に期待される-1を配列が含む場合があるから、内部関数を作ってターゲットがあるか探す
あった場合はそのindexを返す。ない場合は-1を返す。

Discussion