NeetCodeのSolutionを書いていく #
Binary Search #
https://neetcode.io/problems/binary-search
neetcode.io
昇順に並べられた整数のリストと、ターゲットの整数を与えられる。 リストに含まれるターゲットを見つけ、ある場合はそのインデックスを、ない場合は-1を返す関数を作る。
O(logn)時間で解決できる必要がある。
ソート済みだから２分探索すればいいのかな？
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を返す。
Reply by Email