704. Binary Search

1215 ワード
leetcode テキストリンク

これは,targetなどの数字に対応するインデックスを配列中で検索して出力する問題である.
問題ではO(logn)アルゴリズムの使用が明確に要求されている.
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if target not in nums:
                return -1
            elif nums[i] == target:
                return i
最初はO(log n)が何なのか分からなかったのでそうしましたがタイムアウト.
本当にダメだと思い、質問を読み直してO(logn)を検索しましたが、
これはアルゴリズムで、中間値を指定し、対は出力し、小さいか大きいかは範囲を縮小し、出力値を探します.
しかし、どうすればいいか分からないので、いくつかのソリューションを見て、それに従って、細部ごとに運行時間を変えました.

最速のコード
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            m = int((l+r)//2)
            if nums[m] == target: 
                return m
            elif nums[m] <= target:
                l = m+1
            else:
                r = m-1
        return -1
文字数やスペースなどの速度もずいぶん変わりました.
最も重要な時間短縮の原因はm上のintである.
整数であることを事前に指定して時間を短縮するかどうか...不思議
TIL 2 | string, function, math expression
TIL 202111118[第9964便]