0

私の知る限り、while ループで指定されたバイナリ検索は、検索空間の最小値と最大値が等しくなるまで常に検索を続ける必要があります。mxしかし、それをテストすると、常にほとんどのアイテムを既にソートした後、何らかの方法で値を取得するため、無限ループに陥ります-2。

while ループの条件を変更してパッチを当てることができると思いますが、なぜそのままの動作をしているのかを理解しようとしており、目と紙で調べてみましたが、イベントを再現できませんmx = -2。

def insort(seq):
    for a in xrange(1, len(seq)):
        if seq[a] > seq[a - 1]:
            continue
        else:
            mn, mx = 0, a - 1
            while mn != mx:
                pivot = mn + ((mx - mn) / 2)
                if seq[a] > seq[pivot]:
                    mn = pivot + 1
                else:
                    mx = pivot - 1
            seq.insert(mn, seq.pop(a))
4

1 に答える 1

3

注: 私は python 2.7.3 を使用しています。他のバージョンの python で除算の結果が異なるかどうかはわかりません。

いくつかの変更が必要です:

  • mn != mxに変更mn < mx
  • pivot = mn + ((mx - mn) / 2)分割に関しては、ステートメントを変更するpivot = int(math.floor((mn + mx) / 2))かpivot = mn + int(math.floor((mx - mn) / 2))、あらゆる種類の驚きを防止します。
  • で示される検索間隔は、mnでmx指定される半開間隔に変更され[mn, mx)ます。これは、ハンド コーディングされたバイナリ検索に関して、私がよく知っているものだからです。したがって、最初はmxに設定する必要があり、 (iow、テストがの場合)の場合ではなく に設定する必要があります。amxpivotpivot - 1seq[a] <= seq[pivot]ifFalse

したがって、編集を含むコードは次のようになります。

import math

def insort(seq):
    for a in xrange(1, len(seq)):
        if seq[a] > seq[a - 1]:
            continue
        else:
            mn, mx = 0, a
            while mn < mx:
                pivot = mn + int(math.floor(((mx - mn) / 2)))
                if seq[a] > seq[pivot]:
                    mn = pivot + 1
                else:
                    mx = pivot
            seq.insert(mn, seq.pop(a))

元のコードでは、 mxgets でスタックする例を示します-2。

このリストを考えると：[10, 7, 8, 5, 13, 2, 6, 1, 50]

値を持つインデックス 5 の要素まで、すべてが正常に機能します (いくつかのステートメント2を追加して、これを自分で確認してください)。は false (はprintこれまでのところ最小の要素です) であるため、if ステートメントの else 分岐に入ります。seq[a] > seq[a-1]2

この時点で：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = a - 1 = 4

mn != mx( )から0 != 4while ループに入ります。=pivotに設定されています。次に実行します。、while =およびisであるため、else ブランチに移動して実行します0 + ((4 - 0) / 2)2if seq[a] > seq[pivot]seq[a] = 2seq[pivot]82 > 8Falsemx = pivot - 1 = 2 - 1 = 1

この時点で：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = 1

while ループで再度チェックを実行します。mn != mx( 0 != 1) ということで、while ループの本体に入ります。を設定しpivot = 0 + ((1 - 0) / 2) = 0(私は python 2.7 を使用してこの除算を実行しているので、repl で検証します)、チェックseq[a] > seq[pivot]( 2 > 5) を実行します。これはFalseです。したがって、 を設定しmx = pivot - 1 = 0 - 1 = -1ます。

この時点で：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = -1

mn != mxここで、while ループ( )でチェックを行う0 != -1ので、while ループの本体に入ります。pivot = 0 + ((-1 - 0) / 2) = -1. 次に、チェックseq[a] > seq[pivot]( seq[5] > seq[-1]、つまり の 5 番目の要素と の最後の要素を比較する) を実行します。seqつまり2 > 50、 ですFalse。だからmx = pivot - 1 = -1 - 1 = -2。

これで最終ステップに到達しました。

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = -2

while ループのチェックではmn != mx, ということで に進みpivot = 0 + ((-2 - 0) / 2) = -1ます. これが上記のステップと同じピボットであることに注意してください。次に、seq[5] > seq[-1]が実行されます ( 2 > 50) False。だからmx = pivot - 1 = -1 - 1 = -2。そして、上記と同じ状態になります。これが、無限ループが表示される理由です。

最後に、二分探索は、境界インデックスを間違えやすいため、コード化するのが非常に難しいアルゴリズムです。私は何度も手作業でコードを書いてきましたが、それでもかなりトリッキーだと思います。これも読みたいかもしれません: http://en.wikipedia.org/wiki/Binary_search_algorithm

それが役立つことを願っています!

于 2013-08-05T03:26:20.487 に答える