使用二进制递归函数查找列表的索引

-2

因此，我被指示创建一个带有2个参数（一个列表和一个数字）的函数，该函数使用二进制递归搜索来查看数字是否在列表中。如果数字在列表中，我要返回它的索引，如果它不是，我将返回-1。到目前为止，我有使用二进制递归函数查找列表的索引

def findIndex(alist,num): 
    print(alist) 
    if len(alist) % 2 == 0: 
      mid = int((len(alist)/2)-1) 
    else: 
      mid = ((len(alist)//2)) 

    if alist[mid] == num: 
      print(mid) 
    elif alist[mid] > num: 
      findIndex(alist[0:mid],num) 
    elif alist[mid] < num: 
      findIndex(alist[mid+1:],num)

我知道二进制搜索是如何工作的。做到中间，如果它不是你正在搜索的数字，将该数字与你正在搜索的数字进行比较。如果它大于您要搜索的数字，请搜索列表的前半部分。如果较小，则再次搜索列表的后半部分。问题是我的代码只适用于我搜索的数字在每种情况下都小于中间数字的情况。

来源

2017-04-19 Malaikatu Kargbo

分析

有几个问题的逻辑。

被删除的帖子钉住了您最显眼的问题：您的搜索仅在搜索目标出现在一系列只有左侧的分区的中间时有效。否则，你打印0，索引当列表下降到一个单一的项目。
如果目标不在列表中，当您尝试查找空列表的中点时，程序在索引超出范围时崩溃。
你永远不会返回任何东西。打印结果与返回值不同。

SOLUTION

有两种简单的方法来处理这个问题。第一种方法是使用findIndex作为包装函数，然后编写您希望由其调用的函数。例如：

def findIndex(alist,num): 
    return binaryFind(alist, 0, len(alist), num) 

def binaryFind(alist, left, right, target): 
    # Here, you write a typical binary search function 
    # with left & right limits.

第二个是返回找到的索引，但是调整它是为了切断列表左半部分的所有时间。每个级别的调用都必须将该调整添加到返回值，并将总和返回到先前的级别。简单的情况是这样的，当你在列表中的右半部分重复：

elif alist[mid] < num: 
     return (mid+1) + findIndex(alist[mid+1:], num)

这是否让你对一个有用的解决方案移动？

来源

2017-04-19 16:19:39 Prune

使用二进制递归函数查找列表的索引

回答

相关问题