二进制搜索返回目标

的索引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

二进制搜索返回目标

回答

相关问题