二進制搜索返回目標

的索引I必須返回一個數組的目標元素的索引。二進制搜索返回目標

目前，當我搜索是在中點的元素，它返回正確的指標，但對於任何其他元素不爲我工作。

我想我犯了一個錯誤，當我打翻在陣列

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))

來源

2017-02-13 bighead

是有可能，當我找到的元素數組是唯一的那個元素，由於二進制搜索分裂成兩半數組的本質是什麼？ – bighead

那是因爲每次你做一個遞歸調用，不同的修改列表過去了，指數將在每一個電話改變。例如，如果你搜索在陣列的下半年編號，最終返回的值將小於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)))

來源

2017-02-13 13:28:13 Shubham

你的答案失敗的'IndexError'當被問及找到一個比一個不在列表中的值。我編輯了你的答案來解決這個問題，並且編輯你的參數爲kwargs，所以我們不必在每次調用函數時都傳遞它們。 – 0TTT0

您的algortihm給出了最後拆分的列表中的索引。因此，對於你的答案，如果你會打印清單9中，我們會得到如下：

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

至極返回索引1.這是最後的名單[8, 9]正確。通過記住列表的長度可以輕鬆地修復這個問題。

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))

這比以前的解決方案使用的內存少一點。當然這也更快，雖然這是微不足道的。

來源

2017-02-13 13:44:36

嘗試編輯接受的答案，因爲它搜索的數字高於列表中的數字時失敗，但由於某些原因OP不接受編輯，這意味着答案仍然是錯誤。既然如此，我會在這裏公佈答案。這不僅回答解決IndexError當被問及找到一個比一個不在列表中的值，它也改變了參數傳遞給被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))

來源

2017-11-12 18:31:30 0TTT0

二進制搜索返回目標

回答

相關問題