3

私のバージョンの二分探索では、コーナー ケースに問題があります。私のバージョンは、入力リストに 1 を含むビンを出力します。アルゴリズムは、入力リストの半分のサイズのグループ (以下のコードの上部と下部) をそれぞれテストすることでこれを行い、1 の存在が検出された場合、アルゴリズムは通常のバイナリ検索のように参照を移動し、 1 が見つかりました。リストには 1 と 0 のみが含まれます。

注意: any() は O(n) 操作で (サブ) リストをスキャンするため、以下のアルゴリズムの目的 (サブをテストして 1 の位置を特定すること) を無効にしているように見えることが指摘されています。 -リスト)。私は積極的により良いテストを探しており、どんなアイデアでも喜んで聞いていますが、(現在) この問題を解決することに積極的に興味を持っています.

以下は機能です：

def binary_search(inList):
    low = 0
    high = len(inList)

    while low < high:
        mid = (low + high) // 2
        upper = inList[mid:high]
        lower = inList[low:mid]
        if any(lower):
            high = mid
        elif any(upper):
            low = mid+1
       else:
            # Neither side has a 1
            return -1
    return mid

上記のコードがパスする単体テストは次のとおりです。

# Test a basic case
inlist = [0] * 256
inlist[123] = 1
assert binary_search(inlist) == 123

# Test a case with odd len
inlist = [0] * 99
inlist[20] = 1
assert binary_search(inlist) == 20

# Test a case with odd len
inlist = [0] * 100
inlist[20] = 1
assert binary_search(inlist) == 20

inlist = [0]*4
inlist[1] = 1
assert binary_search(inlist) == 1

# Start
inlist = [0] * 256
inlist[0] = 1
assert binary_search(inlist) == 0

##middle
inlist = [0] * 256
inlist[128] = 1
assert binary_search(inlist) == 128

#end
inlist = [0] * 256
inlist[255] = 1
assert binary_search(inlist) == 255

#Test the case with no 1s
inlist = [0] * 8
assert binary_search(inlist) == -1

しかし、このコーナーケースでは失敗します

inlist = [0]*4
inlist[2] = 1
assert binary_search(inlist) == 2

起こっているように見えるのは、最初の段階ですべてが期待どおりに進むということです:

inList = [0,0,1,0]
upper = [1,0]
lower = [0,0]

しかしセカンドステージではミッド、ハイ、ローが全て3になり、

upper = [0]
lower = []

つまり、1 が欠落しています。

デバッガーで 1 時間過ごし、関数を次のように変更しました。

def binary_search(inList)
    low = 0
    high = len(inList) -1
    while low <= high:
        mid = low + (high - low) // 2
        if any(inList[low:mid]):    # <- this one
            high = mid - 1
        elif any(inList[mid + 1:high+1]): # <- this one
            low = mid + 1
        else:
            return mid
    return -1

これで、すべて 0 のテストを除いて、上記のすべてのテスト (および奇妙な cornner ケース) に合格します。

#Test the case with no 1s
inlist = [0] * 8
assert binary_search(inlist) == -1

これはばかげていると思いますが、関数が両方のテストに合格する方法を見つけることができません。

4

3 に答える 3

2

問題は次のとおりです。

while low <= high:
    mid = low + (high - low) // 2
    if any(inList[low:mid]):    # <- this one
        high = mid - 1
    elif any(inList[mid + 1:high+1]): # <- this one
        low = mid + 1
    else:
        return mid

リストにすべての が含まれているとどうなるか考えてみてください0。との間にifがないため、 は失敗します。との間に がないため、 も失敗します。次に、まさに今実行されている があります。したがって、取得できません。1inListlowmidelif1midhighelse-1

あなたのブロックは、 が存在しelseないときに実行されるコードの一部です。したがって、本当にすべての s のケースを処理したい場合は、そのブロックを return にする必要があります。1inList0-1

補足として、並べ替えられていないリストでバイナリ検索に似たようなことをしたい理由がわかりません。

于 2013-07-16T17:43:03.180 に答える
1

二分探索でタスクを解決することは不可能です。下部にある私のコメントを参照してください。ただし、二分探索をほぼ正しく実装したので、それを修正してから、なぜこの問題に適していないのかについて説明しましょう。

これは、コメント付きの (元のバージョンの) 修正バージョンです。全体的な構造は問題なく、これらは 1 つずつ少しずつずれている問題です: たとえば、の代わりに を設定lowする必要があります。midmid+1mid

def binary_search(inList):
    low = 0
    high = len(inList)

    while low < high - 1:  # Iterate while there are at least 2 elements
        mid = (low + high) // 2
        upper = inList[mid:high]
        lower = inList[low:mid]
        if any(lower):
            high = mid
        elif any(upper):
            low = mid  # mid was the first element in upper, so make sure to keep it
        if low == high - 1:
            # Only one element remains now, so it must be the 1
            return low
    return -1

ただし、お気づきのように、 any() を実行すると、リストをスキャンしているため、バイナリ検索のポイント全体が無効になります。

二分探索は、リスト内のすべての要素を調べずに、リスト内の何かを見つける方法です。それはどのように可能ですか？リストがソートされている場合のみ。二分探索は、あなたがやっているように、リストを繰り返し半分に分割しますが、 とをmid調べずに を見るだけです。lowerupper

于 2013-07-16T17:48:53.870 に答える