调试一步一步Trinary搜索

这是我的代码。调试一步一步Trinary搜索

def trin_search(A,first,last,target): 
    #returns index of target in A, if present 
    #returns -1 if target is not present in A 
    if first>last: 
     return -1 
    else: 
     one_third=first+(last-first/3) 
     two_thirds=first+2*(last-first)/3 
     if A[one_third]==target: 
      return one_third 
     elif A[one_third]>target: 
      #search the left-hand third 
      return trin_search(A,first, one_third-1],target) 
     elif A[two_thirds]==target: 
      return two_thirds 
     elif A[two_thirds]>target: 
      #search the middle third 
      return trin_search(A,one_third+1,two_thirds-1,target) 
     else: 
      #search the right-hand third 
      return trin_search(A,two_thirds+1,last,target)

这是一个三元递归搜索。我不断收到此错误：

line 24, in trin_search 
if A[one_third]==target:IndexError: list index out of range

但我无法想象为什么。以下是我如何在外壳中运行程序：

>>>> A=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] 
>>>> trin_search(A,A[0],A[len(A)-1],5)

任何帮助，非常感谢。

来源

2013-01-18 Unknown

问题是什么？ –

抱歉在编辑完成之前意外提交了。 – Unknown

您是否尝试过从函数调用中打印函数参数以查看哪个递归调用正在生成错误？ – bogatron

问题是在行one_third=first+(last-first/3)。这里，first == 1 so first/3 == 0和表达式变成first+last，这是21，因此明显超出范围。你想要的表达是first+(last-first)/3。（在你的代码中还有一些其他的问题，比如使用列表中的值而不是索引来调用函数。）

来源

2013-01-18 17:49:36

是的，像这样的函数通常分别设置为默认'first'和'last'分别为'0'和'len（A）'，以便于基本情况的使用。 –

调试一步一步Trinary搜索

回答

相关问题