1

二分探索を実装しようとしています。順序付けられたリストを取得し、中間値を取得してターゲット値と比較し、ターゲットが見つかるかリストから欠落するまで、中間値の上または下にサブリストを作成します。ただし、何らかの理由で、中間点がターゲットでない限り、常に「なし」が返されます。何が問題なのかわかりません。

def bisect(list,target):


    print list
    split= list[len(list)//2]
    print "Split value : " + str(split)  

    if target==split: 
        return "target" 

    elif target<split:
        bisect(list[:split],target) 

    elif target>split:
        bisect(list[(split):],target)

a= [1,2,3,4,5,6,7,8,9,10]       
print bisect(a,2)

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Split value : 6
[1, 2, 3, 4, 5, 6]
Split value : 4
[1, 2, 3, 4]
Split value : 3
[1, 2, 3]
Split value : 2
None

分割とターゲット値の間の最後の比較が行われていないように見えますか?

4

1 に答える 1

4

2 つの問題:

  1. を呼び出して再帰する場合でも、 を実行して呼び出しの値を返すbisect必要があります。return bisect(list[:split],target)

  2. splitは の要素でlistあり、インデックスでlist[:split]はないため、あなたの考えは実行されません。代わりに使用list[:len(list)//2]し、同様に に変更list[split:]しlist[len(list)//2:]ます。

于 2013-05-10T19:17:42.437 に答える