1

targetリストまたはタプル内の値、、のバイナリ検索を実行するために、次のコードを記述しましたcollection。

def binary(collection, target):
    """Binary search
    Takes a sorted list or tuple, collection, then searches for target
    Returns -1 if item isn't found. """
    length = len(collection)
    minimum = 0
    maximum = length - 1
    while minimum <= maximum:
        pivot = (minimum + maximum) // 2
        if collection[pivot] is target:
            return pivot
        elif collection[pivot] > target:
            minimum = pivot + 1
        else:
            maximum = pivot - 1
    return -1

ご覧のとおり、にtargetが見つからない場合collection、関数は-1を返します。私が何をしたかに関係なく、関数は-1を返しました。

>>> test = [1, 2, 3, 4, 5, 6]
>>> binary(test, 5)
-1
>>> binary(test, 1)
-1

この問題の原因は何ですか？

4

2 に答える 2

4

あなたはこの状態を逆に持っています：

elif collection[pivot] > target:

切り替えると、検索が機能します。

elif collection[pivot] < target:

何が価値があるのか​​、何が起こっているのかを確認するために検索にプリントアウトを追加することでこれを理解しました。疑わしい場合は、プリントアウトを追加してください。

>>> binary([1, 2, 3], 1)
(min=0, max=2, pivot=1)
(min=2, max=2, pivot=2)
     ^ Oops

# After fixing...
>>> binary([1, 2, 3], 1)
(min=0, max=2, pivot=1)
(min=0, max=0, pivot=0)

ちなみに、内蔵のバイセクトモジュールは二分探索を行います。教育的価値のためにそれをしているのでない限り、あなたはあなた自身を書く必要はありません。

于 2010-09-11T05:22:04.527 に答える
1

条件テストをに修正することに加えてelif collection[pivot] < target:、「is」演算子を使用して、ターゲットアイテムが見つかったかどうかをテストしました。

    if collection[pivot] is target:

代わりに「==」を使用する必要があります。

    if collection[pivot] == target:

「is」を使用すると、2つのものが実際に同じオブジェクトであるかどうかがテストされます。Pythonでは、小さな文字列と整数のオブジェクトが保存およびリサイクルされることがよくあるため、これでうまくいく可能性があります。ただし、ほとんどの場合、次のことは行われません。

>>> a='abc'
>>> id(a)
2129839392
>>> b='ab'
>>> b+='c'
>>> id(b)
2129963136
>>> a
'abc'
>>> b
'abc'
>>> binary([a],a)
0
>>> binary([a],b)
-1
于 2011-02-16T20:01:12.010 に答える