0

こんばんは。私はプログラミングに戻ろうとしていて、自分の時間にコーディングの練習をすることにしました。現在、バイナリ検索を実装しようとしていますが、コードに継続的なループがあるようです。誰かが私に何が起こっているのかについてのヒントを教えてもらえますか？

def binChop(key, ordered_set):

    found = False
    newSet = ordered_set

    while found != True or newSet > 0:
        midpoint = int(len(newSet)/2)
        if key < newSet[midpoint]:
            found = False
            newSet = newSet[:midpoint]
        elif key > newSet[midpoint]:
            found = False
            newSet = newSet[midpoint:]
        elif key==newSet[midpoint]:
            found = True
    return found
4

3 に答える 3

1

あなたにはいくつかの問題があり、いくつかは改善することができます：

  • 要素が順序付きリストにない場合にバイナリ検索を正しく実行するには、左右の境界インデックスが必要です。ここで正しいアルゴリズムを参照してください。キーを見つけるか、左側の境界が右側の境界の右側にあるか、またはその逆の場合は、whileループから抜け出します（max_point < min_point）。
  • は必要ありませんnewSet。ソートされたリストへのインデックスはいつでも使用できます。したがって、mid_pointは単なるインデックスであり、min_point（左側の境界）とmax_point（右側の境界）も同様です。
  • 二分探索は通常、キーのインデックスをreturnとして返します。見つからない場合は、を返し-1ます。

私のPythonコードは次のように表示されます：

def binChop(key, ordered_list):

    min_point, max_point = 0, len(ordered_list)-1

    while min_point <= max_point:
        mid_point = (min_point+max_point)/2

        if ordered_list[mid_point] < key:
            min_point += 1
        elif ordered_list[mid_point] > key:
            max_point -= 1
        else:
            return mid_point
    return -1

test_cases = [[], [5], [4,5], [5,6], [1,5,6], [1], [1,4], [1,6,15]]
for ordered_list in test_cases:
    print "%-10s %5s" % (ordered_list, binChop(5, ordered_list))

Outputs:
list       index of 5
[]            -1
[5]            0
[4, 5]         1
[5, 6]         0
[1, 5, 6]      1
[1]           -1
[1, 4]        -1
[1, 6, 15]    -1
于 2012-11-01T05:47:24.063 に答える
1

「newSet > 0」は常に真だと思います。標準の python セットの場合、エラーが発生します。

>>> b=set()
>>> b
set([])
>>> b > 0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only compare to a set

しかし、そうではないので、リストまたはタプルだと思います：

>>> a=[]
>>> a > 0
True
>>> b=()
>>> b > 0
True

どちらもあなたが期待することをしません(長さをチェックします)。

一般に、コードに追加import pdb; pdb.set_trace()し、ステップ実行してバグを見つけます。

于 2012-10-31T22:12:57.450 に答える
1

あなたの問題はwhileループの状態にあると思います。「and」ではなく「or」があります。これは、結果が見つかったとしても、newSet>0 条件が満たされることを意味します。

于 2012-10-31T22:11:17.803 に答える