Pythonでのバイナリ検索の実装

Question

バイナリ検索を使用してソリューションを実装しようとしています。範囲外のインデックス：私は、私はこの

def searchBinary(list, sval): 
    low = 0 
    high = len(list) 

    while low < high: 
     mid = low + math.floor((high - low)/2) 

     if list[mid] == sval: 
      print("found : ", sval) 
     elif l2s[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

のようなものを書かれているが、私はこれを実装しようとしていたとき、私のようなエラーを取得しています

list = [1, 2, 3, 4, 6] 
value to be searched = 2 

番号のリストを持っています。問題の特定にご協力ください。

Answer 1

いくつかあります。

1. 名前が矛盾しています。また、変数名としてlistを使用しないでください。グローバルな組み込み関数をシャドーイングしています。

2. 停止条件はwhile low <= highです。これは重要。

3. 値を見つけたら壊れません。これにより、無限の再帰が発生します。

---

def searchBinary(l2s, sval): # do not use 'list' as a variable 
    low = 0 
    high = len(l2s) 

    while low <= high: # this is the main issue. As long as low is not greater than high, the while loop must run 
     mid = (high + low) // 2 

     if l2s[mid] == sval: 
      print("found : ", sval) 
      return 
     elif l2s[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

そして今、

list_ = [1, 2, 3, 4, 6] 
searchBinary(list_, 2) 

出力：以下のコメントあたり

found : 2 

Answer 2

UPDATEhigh = len(lst) - 1。

---

3つの問題：

1. あなたはl2s代わりのlist（パラメータの実際の名前）を使用。
2. whileの条件は、ではなく、low <= highである必要があります。
3. おそらく、値が見つかったときにインデックスを返すか、見つからない場合はNone（おそらく-1？）を返します。

私が作ったカップルの他の小さな変更：

• それはビルトインlistを隠すために悪い考えです。私はパラメータをlstに変更しました。これはこの状況でPythonでよく使用されています。
• mid = (low + high) // 2は、中間点を見つける簡単な形式です。
• Pythonの規約では、camelCaseではなくsnake_caseを使用するため、関数の名前を変更しました。

固定コード：

def binary_search(lst, sval): 
    low = 0 
    high = len(lst) - 1 

    while low <= high: 
     mid = (low + high) // 2 

     if lst[mid] == sval: 
      return mid 
     elif lst[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

    return None 

print(binary_search([1, 2, 3, 4, 6], 2)) # 1