[探索バイナリ]Let code 704.Binary Search

道路標識704号
ソート配列のターゲット値を検索し、インデックス値を返します.
復帰する

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        def BS(left, right):
            if left > right:
                return -1

            mid = left + (right - left) // 2
            if nums[mid] == target :
                return mid
            elif nums[mid] > target :
                return BS(left, mid-1)
            else:
                return BS(mid+1, right)

        return BS(0, len(nums)-1)

pythonの再帰呼び出しの最大数は、1000回の再帰アルゴリズムの作成時の数を超えないことに注意してください.

複文

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target :
                return mid
            elif nums[mid] > target :
                right = mid -1
            else:
                left = mid + 1

        return -1

バイナリ検索アルゴリズムのエラー
バイナリ探索アルゴリズムでは,中値を求める式を(左+右)/2と書く.これは両端のインデックスの平均値を求めて、とても直観的で熟知しています
ただし,資料型では最値が規定されているため,intの最大値が左+右を超えるとエラーが発生する.
従って,解決策はleft+(right−lef)/2である.すなわち,左側に2つの間隔の半分を加算する方式を選択してオーバーフロー問題を解決する.
これは長い間誰も気づかなかった間違いにすぎない......ほほほ