バイナリ検索を使用してターゲットのインデックスを返す

Question

配列のターゲット要素のインデックスを返す必要があります。

現在、中点にある要素を検索すると、正しいインデックスが返されますが、他の要素の場合は、私のためには機能しません。

私は私はあなたが再帰呼び出しを行うたびに、異なる修正リストが渡され、インデックスがすべての呼び出しに変更されるためである配列

aList = [1,3,5,6,8,9,10,12,34,56,78,456] 
def recursiveBinarySearch(aList, target): 
    #aList = sorted(aList) 

    if len(aList) == 0: 
     return False 
    else: 
     midpoint = len(aList) // 2 
     if aList[midpoint] == target: 
      return aList.index(target) 
     else: 
      if target < aList[midpoint]: 
       return recursiveBinarySearch(aList[:midpoint],target) 
      else: 
       return recursiveBinarySearch(aList[midpoint+1:],target) 

print(recursiveBinarySearch(aList,9)) 

Answer 1

をこぼしたとき、私は間違いを犯していと思います。たとえば、配列の後半で数値を検索すると、配列のこの部分だけが次の繰り返しで渡されるため、最終的な戻り値はlen(aList)/2より小さくなります。

回避策は、リストを分割する代わりにリストのstartとendポイントを渡すことです。

aList = [1,3,5,6,8,9,10,12,34,56,78,456] 
def recursiveBinarySearch(aList, target, start, end): 
    #aList = sorted(aList) 

    if end-start+1 <= 0: 
     return False 
    else: 
     midpoint = start + (end - start) // 2 
     if aList[midpoint] == target: 
      return midpoint 
     else: 
      if target < aList[midpoint]: 
       return recursiveBinarySearch(aList, target, start, midpoint-1) 
      else: 
       return recursiveBinarySearch(aList ,target, midpoint+1, end) 

print(recursiveBinarySearch(aList,455, 0, len(aList))) 

Answer 2

あなたのalgortihmは最後の分割リストにインデックスを与えます。あなたは9のためのリストを印刷するかどう だからあなたの答えのために、我々は次のようになるだろう：

[1, 3, 5, 6, 8, 9, 10, 12, 34, 56, 78, 456] 
[1, 3, 5, 6, 8, 9] 
[8, 9] 

WICHは、最後のリスト[8, 9]ための正しいインデックス1を返します。 これは、リストの長さを記憶することによって簡単に修正できます。

aList = [1,3,5,6,8,9,10,12,34,56,78,456] 
def recursiveBinarySearch(aList, target, index): 
    #aList = sorted(aList) 

    if len(aList) == 0: 
     return False 
    else: 
     midpoint = len(aList) // 2 

     if aList[midpoint] == target: 
      return aList.index(target)+index 
     else: 
      if target < aList[midpoint]: 
       return recursiveBinarySearch(aList[:midpoint],target, index) 
      else: 
       return recursiveBinarySearch(aList[midpoint:],target, index+len(aList[:midpoint])) 


print(recursiveBinarySearch(aList,56,0)) 

これは、以前のソリューションよりも少し少ないメモリを使用します。もちろん、それは余りにも速いものの、それも速いです。

Answer 3

リスト内の数値よりも高い数値を検索すると失敗しますが、何らかの理由でOPが編集を受け入れないため、答えがまだであることを意味します。その場合、私はここに答えを掲示するでしょう。この回答は、リストにない値より大きい値を見つけるよう求められたときにIndexErrorを修正するだけでなく、関数を呼び出すたびにそれらを渡す必要がないようにargsをkwargsに変更します。

aList = [-1,1,3,5,6,8,9,10,12,34,56,78,456] 

def binary_search(arr,item,low = 0, high = None): 
    if high == None: 
     high = len(arr) 
    mid = low + (high-low) //2 
    if high - low + 1 <= 0 or mid==high: 
     return False 
    else: 
     guess = arr[mid] 
     if guess == item: 
      return mid 
     if item < guess: 
      return binary_search(arr, item, low, mid) 
     else: 
      return binary_search(arr, item, (mid+1), high) 

(binary_search(aList,457))