0

これが私のコードです。

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)

どんな助けでも大歓迎です。

4

1 に答える 1

2

問題は行にありone_third=first+(last-first/3)ます。first == 1これfirst/3 == 0は21でfirst+lastあり、明らかに範囲外です。欲しい表現はfirst+(last-first)/3. (インデックスの代わりにリストからの値を使用して関数を呼び出すなど、コードには他にもいくつかの問題があります。)

于 2013-01-18T17:49:36.200 に答える