バイナリ検索Pythonなぜmid + 1かmid-1を使用するのですか

Question

私はバイナリ検索を学習していますが、サンプルコードでは "low = mid +1 and high = mid -1"を使用していますが、代わりに "low = mid and high = mid"

def binarysearch(sequence, value): 
    lo, hi = 0, len(sequence) - 1 
    while lo <= hi: 
     mid = (lo + hi) // 2 
     if sequence[mid] < value: 
      lo = mid + 1 
     elif value < sequence[mid]: 
      hi = mid - 1 
     else: 
      return mid 
    return None 

my_list = [1, 3, 5, 7, 9] 
binarysearch(my_list, 3) 

Answer 1

なぜなら、重複する検索を避けるためです。まだチェックされていない項目に検索範囲の境界線を配置します。例えば

：ミッドはインデックス10である場合、左の次の検索は、インデックス9までの値を見て、インデックス11

    mid 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
|     | |       | 
<-from 0 to mid-1-> <-- from mid+1 to the end --> 

note that in this example, the boundary values are included   

Answer 2

での値から右に検索されます私が説明しようとさせてくださいバイナリ検索が動作する理由我々は我々が持っているでしょう、次の順序A=[-5, 10, 14, 33, 42, 42, 42]とsearched_value = 14をしましたとしましょう：

Iteration 1,  lo = 0, hi = 6, mid = 3  A[mid] > 14 
Iteration 2,  lo = 0, hi = 2, mid = 1  A[mid] < 14 
Iteration 3,  lo = 2, hi = 2, mid = 2  A[mid] = 14 (found!) 

アルゴリズムの各反復において、我々はloとhiは常に検索値の位置を含んでおり、我々はそれを証明するだろうと結論できました

誘導仮説：繰り返しの数に誘導することにより、検索値は、それが常にloとhiの間に含まれる配列中に存在する場合。

基本事例：検索値は、それがloとhiの間に含まれることがあります配列中に存在する、そして不変は自明正しいかどう反復1 lo = 0とhi = n-1では、結果のすべての要素が含まれています。

誘導ステップ：検索値がloとhiの間に含まれている場合いずれかの段階で、それは次の反復でloとhiの間に含まれることを継続します。この場合、アルゴリズムが正しく順序で検索値の位置を報告し終了して検索するので不変が正しい：A[mid] = searched_value場合

• ：我々は3つの可能性（と、ここで質問に対する答えですが）しました値はloとhiの間でした。
• A[mid] < searched_value場合
：それはソート順序だことを知って、（ A[mid]含む） A[lo...mid] < searched_value間のすべての要素は、したがって、私たちは lo=mid+1（安全上半分にのみ検索）を割り当てることができますし、不変は、まだ次の反復で正しいでしょう。
• A[mid] > searched_value場合
：それはソート順序だことを知って、（ A[mid]含む） A[mid...hi] > searched value間のすべての要素は、したがって、私たちは、 hi=mid-1（安全に下半分のみを検索）ASSINGことができ、不変は、まだ次の反復で正しいでしょう。 、各反復において、アルゴリズムは常に小さなセグメントシーケンスの に検索すること searched_valueであるか、それは違うと、次の反復であるだけで1要素がどちらかありますので、終了条件が保証され、与えられた

アルゴリズムはそのような要素がシーケンスに存在しないことを報告することになる。

結果的にアルゴリズムは正しいと証明されます（また、mid+1とmid-1を使用する理由も証明されています）。