Skip to main content
 首页 » 编程设计

python之如何在 python (递归) 中进行二进制搜索,但不包括列表的最大值和最小值

2024年11月01日19freeliver54

我一直想进行二进制搜索(通过递归),但我不知道为什么我的代码不起作用... 任何人都可以请更正我的代码并说明它不起作用的原因吗??

正如您在我的代码中看到的那样,我在每次递归时对字符串进行切片,最后当找到目标时,我将返回目标的位置..

def binary(n,target): 
    n.sort() 
    mid = (0 + (len(n)-1))//2 
    if target == n[mid]: 
        return mid 
    elif target < n[mid]: 
        return binary(n[:mid],target) 
    elif target > n[mid]: 
        return binary(n[mid:],target) 

这是我收到的错误信息... RecursionError:调用 Python 对象时超出最大递归深度。

请您参考如下方法:

有两个问题,都在最后一行:

def binary(n, target): 
    n.sort() 
    mid = (0 + (len(n) - 1)) // 2 
    if target == n[mid]: 
        return mid 
    elif target < n[mid]: 
        return binary(n[:mid], target) 
    elif target > n[mid]: 
        return mid + 1 + binary(n[mid + 1:],target) 
                ^^^^^^^^                ^ 
  1. 由于您正在切片,并且为了在原始排序列表中提供索引,我们需要跟踪我们在递归时“丢失”的索引
  2. n[:mid] 的完整形式是 n[mid+1:] - 而不是 n[mid:] 因为你已经检查目标(在中间)并希望将其从 future 的迭代中删除 - 顺便说一下,这是导致无限循环的原因!

由于我们在 mid+1 处对列表进行切片,因此我们需要在递归调用之前添加 mid+1,以便保留列表右侧的项目索引:

[1,2,3,4,5] 
     ^ say we slice here and get [4,5] 
       we want to save the indexes so we'll add mid (2) + 1 since now in [4,5] the item 4 will get the index zero 

评论:通过在每次迭代时调用 n.sort(),我们“失去”了二进制搜索的所有优势,因为即使在列表排序之后,重新排序也至少需要在)。因此,如果我们需要先排序,我们不妨迭代数组直到找到/找不到该项目。或者,如果我们坚持排序,只做一次,然后才递归调用:

n.sort() 
binary(n, 2) 

binary 不再包含排序:

def binary(n, target): 
    mid = (0 + (len(n) - 1)) // 2 
    if target == n[mid]: 
        return mid 
    elif target < n[mid]: 
        return binary(n[:mid], target) 
    elif target > n[mid]: 
        return mid + 1 + binary(n[mid + 1:], target)