Python的 - 改变我的二进制搜索功能

我写了下面的代码：Python的 - 改变我的二进制搜索功能

def binary_search(key,lst): 
    """ iterative binary search 
     lst better be sorted for binary search to work""" 
    n=len(lst) 
    lower=0 
    upper=n-1 
    outcome=None # default value 
    while lower<=upper: 
     middle=(upper+lower)//2 
     if key==lst[middle].name: # item found 
      outcome=lst[middle] 
      break # gets out of the loop if key was found 
     elif key<lst[middle].name: # item cannot be in top half 
      upper=middle-1 
     else:  # item cannot be in bottom half 
      lower=middle+1   
    return outcome

我试图改变它，以使其将列表3份，而不是2 我的意思是它不会可以进行二分搜索，但是对于每次迭代，算法会将列表分成3个部分。

我无法执行此操作。

任何帮助将不胜感激。

来源

2013-04-09 Matthew D

你为什么要分成三部分？二进制搜索的优点是你不需要做太多的比较（每次迭代只需要一次）。有三个部分，你需要在很多情况下做两个比较（如果第一个比较结果给出了合适的结果，你可能会发生短路），这大大减少了搜索空间从1/2到1/3的好处迭代。 – Blckknght 2013-04-09 19:11:11

这是一项任务。我知道这不是更有效率。 – 2013-04-09 19:20:53

您需要将列表分成3部分，因为您需要两个middles：upper_middle和lower_middle。你需要为你的if添加更多的子句。如果它小于中下部，那么它是前三分之一，如果它高于上三分之一，那么它是中三分之一。

请记住，即使这是一个很好的编程练习，它并不是真的更有效，因为函数的顺序保持不变（log n）。

来源

2013-04-09 19:11:04

谢谢，我会试试这个。 – 2013-04-09 19:21:28

我试过了，我仍然无法像你所描述的那样真正把握它。你的意思是我应该有3个部分的名单？中间，上中，下中？我希望替代我自己的代码为这项搜索工作，而不是写一个全新的代码，那么你能指导我多一点？我无法将限制设置为默认值，并知道如何检查密钥是否存在。 – 2013-04-10 08:24:26

是的，你需要三个部分的名单。你需要重写整个函数。没有必要避免这种情况，你需要这样做，否则它不会成为三级搜索。 – 2013-04-10 20:17:44

Python的 - 改变我的二进制搜索功能

回答

相关问题