理解私は<em>のPython</em>に非常に新しいですとアルゴリズムを習得しようとしているPythonでループ

Question

ながら、私は何であるか、それは論理的に間違っている私はlow < hiを使用する場合は、リスト上で探していたときに、なぜ、正しい論理演算がlow <= hiでお願いしたかったですそれが防止しているエッジケース。我々は「< =」を使用して代わりにさ

def binary_search(input_array, value): 
    """Your code goes here.""" 
    #O(log(n)) 
    low = 0 
    hi = len(input_array) - 1 
    while low <= hi: #why cant it be low < hi 
     mid = (low + hi)//2 
     if input_array[mid] == value: 
      return mid 
     elif input_array[mid] < value: 
      print(low, hi) 
      low = mid + 1 
     else: 
      hi = mid - 1 
    return -1 


test_list = [1,3,9,11,15,19,29] 
test_val1 = 25 
test_val2 = 15 
print(binary_search(test_list, test_val1)) 
print(binary_search(test_list, test_val2)) 

Answer 1

を返し、15：

第一反復インデックスを： low == 4,hi == 6

第2の反復インデックス：low == 4,hi == 4

あなたが低<高を使用する場合は、4つの< 4戻りfalse以来、2回目の繰り返しであなたのループにドロップしません。あなたのプログラムは、あなたが実際に
hi = len(input_array)
while low < hi: # now this works.
...


を書いていた場合は、一般的に、これは、それは私が、一般的にこれらのループを記述する方法だ可能性値は、インデックス4

Answer 2

単に「<」所望の値が最後のインデックスを（低い= HI）であることを起こる場合には、我々は、に等しい記号を含める必要がありますのでその場合を確認してください。

Answer 3

[1]という要素が1つしかなく、1を検索しているとします。

<：あなただけのループに

<=を飛ばしますので-1を返す：あなたのターゲットがある場合は、あなたの場合には、たとえば、正しい値

Answer 4

上であっても、それは価値を見つけることができないと思うだろう。 len()が常に最後のインデックスよりも1だけ多いことを利用し、その値が<の値の間だけループを実行します。

hiの最大値が配列の最後のインデックスであるように、あなたがlen(input_array)から1を減算した場合、その最後の要素にループを台無しにするために、あなたはlow <= hi

の=一部を必要とします一般に、hi = len(input_array)を最後のインデックスを超えて1に設定してから、low<hiの間だけループを実行するのが（精神的に）簡単です。
（タイピングが少なく、精神的な体操が少ない）
この場合、一度low==hi最後のインデックスを過ぎてしまえば、範囲外になります。

「エッジケース」とは、すべての要素（インデックス）でループを実行することを確認することです。 だからこそ、配列の最後のインデックス/要素を見る必要があります。

これをコード化する一般的な方法は2つありますが、混在させることはできません。あなたの最終状態があなたの初期状態に関係していることを確認してください。あなたが（配列、または配列の最後のインデックスのいずれかの長さ）にhiを設定すると、あなたはlow < hiまたはlow <= hi