61

二分探索は見た目よりも実装が難しいです。「二分探索の基本的な考え方は比較的単純ですが、詳細は驚くほどトリッキーになる可能性があります…」—ドナルドクヌース。

新しいバイナリ検索の実装に導入される可能性が最も高いバグはどれですか？

4

7 に答える 7

74

この質問は、最近再び尋ねられたばかりです。「バイナリ サーチの基本的な考え方は比較的単純ですが、詳細は驚くほどトリッキーになる可能性があります」という Knuth の引用とは別に、バイナリ サーチが最初に公開されたという驚くべき歴史的事実 (TAOCP、第 3 巻、セクション 6.2.1 を参照) があります。 1946 年ですが、バグのない最初の二分探索が公開されたのは 1962 年でした。Bentley の経験によると、ベル研究所や IBM などのプロのプログラマー向けのコースで二分探索を割り当て、2 時間与えたところ、誰もが正しく理解したと報告しました。彼らのコードを調べると、彼らの 90% にバグがありました — 年々。

おそらく、非常に多くのプログラマーが二分探索で間違いを犯す基本的な理由は、スタージョンの法則に加えて、彼らが十分に注意を払っていないことです: with the bugs」アプローチ。そして、エラーの余地がたくさんあります。ここで他のいくつかの回答が言及しているオーバーフローエラーだけでなく、論理エラーです。

以下は、二分探索エラーの例です。これは決して網羅的なものではありません。(トルストイがアンナ・カレーニナで書いているように、 「幸せな家庭はどれも似ている。不幸な家庭はそれぞれ、それぞれのやり方で不幸である」 - すべての間違った二分探索プログラムは、それぞれのやり方で間違っている。)

パティス

次の Pascal コードは、Richard E Pattis による紙のTextbook errors in binarysearching (1988) からの抜粋です。彼は 20 冊の教科書を見て、次のバイナリ検索を思いつきました (ちなみに、Pascal は 1 から始まる配列インデックスを使用します)。

PROCEDURE BinarySearch (A         : anArray,
                        Size      : anArraySize,
                        Key       : INTEGER,
                        VAR Found : BOOLEAN;
                        VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN         
   LOW := 1;
   High := Size;
   
   REPEAT
      Index := (Low + High) DIV 2;
      If Key < A[Index]
         THEN High := Index - 1
         ELSE Low  := Index + 1
   UNTIL (Low > High) OR (Key = A[Index]);

   FOUND := (Low <= High)
END;

大丈夫ですか？これには複数のエラーがあります。先に進む前に、それらがすべて見つかるかどうかを確認してください。初めて Pascal を見た人でも、コードが何をするかを推測できるはずです。

彼は、多くのプログラムに見られる 5 つのエラー、特に上記のプログラムに見られるエラーについて説明しています。

エラー 1 : O(log n) 時間 (n = サイズ) で実行されません。適切なプログラミングの実践に熱心に取り組んでいるプログラマーの中には、二分探索を関数/手順として記述し、それを配列として渡すものがあります。(これは Pascal に固有のものではありません。C++ でベクトルを参照ではなく値で渡すことを想像してください。) これは、配列をプロシージャに渡すだけの Θ(n) 時間であり、目的全体を無効にします。さらに悪いことに、何人かの著者は明らかに再帰的二分探索を行い、毎回配列を渡し、実行時間を Θ(n log n) とします。(これは大げさではありません。実際にこのようなコードを見たことがあります。)

エラー 2 : サイズ = 0 の場合に失敗します。これで問題ない可能性があります。ただし、目的のアプリケーションによっては、検索されるリスト/テーブルが0 に縮小される可能性があり、どこかで処理する必要があります。

エラー 3 : 答えが間違っています。ループの最後の反復が Low=High で始まる場合 (たとえば、Size=1 の場合) は常に、Key配列内にある場合でも、Found:=False を設定します。

エラー 4 :Keyが配列の最小要素より小さい場合は常にエラーが発生します。( Index1になった後High、0にする等、範囲外エラーとなります。)

エラー 5 :Keyが配列の最大要素より大きい場合は常にエラーが発生します。( になった後Index、Size+1 などSizeに設定します。範囲外エラーが発生します。)Low

彼はまた、これらのエラーを「修正」するいくつかの明白な方法が間違っていることが判明したことも指摘しています。実際のコードにもこのような性質があることがよくあります。プログラマーが何か間違ったことを書き、エラーを見つけて、十分に考えずに正しいと思われるまでそれを「修正」した場合です。

彼が試した 20 冊の教科書のうち、2 分探索が正しく行われたのは 5 冊だけでした。残りの 15 個 (皮肉なことに彼は 16 個と言います) で、エラー 1 のインスタンスが 11 個、エラー 2 のインスタンスが 6 個、エラー 3 とエラー 4 がそれぞれ 2 個、エラー 5 のインスタンスが 1 個見つかりました。それらのいくつかには複数のエラーがあったためです。

その他の例

バイナリ検索は、配列を検索して値が含まれているかどうかを確認するだけでなく、ここでもう 1 つの例を示します。もっと考えたら、このリストを更新するかもしれません。

t増加する (減少しない) 関数 f: R->R があり、(たとえば、f の根が必要なため) となるような最大のものを見つけたいとしますf(t) < 0。以下で見つけられるバグの数を確認してください。

float high = INF, low = 0;
while(high != low) {
   float mid = (low + high)/2;
   if(f(mid)>0) high=mid;
   else low=mid;
}
printf("%f", high);

(一部: [0,INF] にそのような t がない可能性があります。f間隔で 0 の場合、これは間違っています。浮動小数点数を等しいかどうか比較しないなど。)

二分探索の書き方

私はこれらのエラーのいくつかを犯していました.2分探索を書いた最初の数十回（時間のプレッシャーのあるプログラミングコンテスト中）、約30％の時間でどこかにバグがありました.正しく。それ以来、二分探索を間違えたことはありません（思い出したように）。トリックは非常に簡単です。

不変条件を維持します。

「低」変数と「高」変数がループ全体 (前、中、後) を満たす不変のプロパティを見つけて決定し、明示的にします。決して違反していないことを確認してください。もちろん、終了条件についても考える必要があります。これについては、準形式的な方法から二分探索プログラムを導出するProgramming Pearlsの第 4 章で詳細に説明されています。

たとえば、調べている条件を少し抽象化するために、xある条件poss(x)が真である最大の整数値を見つけたいとします。この問題定義の明快さでさえ、多くのプログラマーが最初から考えている以上のものです。(たとえば、はある値 に対してでposs(x)ある可能性があります。これは、並べ替えられた配列内のいくつの要素が よりも大きいかを調べることです。) 次に、二分探索を記述する 1 つの方法は次のとおりです。a[x] ≤ vvav

int lo=0, hi=n;
//INVARIANT: poss(lo) is true, poss(hi) is false
//Check and ensure invariant before starting binary search
assert(poss(lo)==true);
assert(poss(hi)==false);
while(hi-lo>1) {
    int mid = lo + (hi-lo)/2;
    if(poss(mid)) lo = mid;
    else hi = mid;
}
printf("%d \n",lo);

assert ステートメントやその他のチェックを追加することもできますが、基本的な考え方は、それが true であることがわかっている場合にのみlo更新するため、常に trueである不変式を維持するということです。同様に、が false の場合のみに設定するため、常に falseである不変式を維持します。終了条件は別途考えてください。(when is 1,は と同じであることに注意してください。したがって、ループを のように記述しないでください。そうしないと、無限ループが発生します。) ループの最後では、が最大でも 1 であることが保証されます。常に維持されている不変式 (は true であり、mid poss(mid)poss(lo)himidposs(mid)poss(hi)hi-lomidlowhile(hi>lo)hi-loposs(lo)poss(hi)は false)、0 にすることはできません。また、不変式のため、それloが返す/出力する/使用する値であることがわかります。もちろん、バイナリ検索を作成する方法は他にもありますが、不変条件を維持することは、常に役立つトリック/規律です。

于 2011-06-18T01:49:15.377 に答える
35

これが私が考えることができるいくつかです：

  • 次の間隔の境界を決定するときのオフバイワンエラー
  • 配列内の最初の等しいアイテムを返すと想定されているが、代わりに後続の等しいアイテムを返した場合の重複アイテムの処理
  • 巨大な配列を使用した、インデックスを計算する際の数値のアンダーフロー/オーバーフロー
  • 再帰的実装と非再帰的実装、考慮すべき設計上の選択

これらはあなたが考えていることですか？

于 2009-02-02T18:38:29.590 に答える
16

これを読んでください。Java の二分探索の実装は、誰かが発見するまでのほぼ 10 年間、バグを隠していました。

バグは整数オーバーフローです。十分な大きさのデータ構造を検索する人はほとんどいなかったので、問題は発生しませんでした。

于 2009-02-02T18:41:02.330 に答える
4

人々が二分探索を正しく実装できない重大な理由の 1 つは、二分探索を適切に特徴付けていないことです。これは明確に定義された問題ですが、通常は適切に定義されていません。

普遍的なルールの 1 つは、失敗から学ぶことです。ここで、「無効な」ケースについて考えると、問題を明確にするのに役立ちます。入力が空の場合はどうなりますか? 入力に重複が含まれている場合はどうなりますか? 反復ごとに 1 つの条件付きテストまたは 2 つのテスト (および早期終了のための追加のテスト) で実装する必要がありますか? インデックスの計算における数値のオーバーフロー/アンダーフローやその他のトリックなどのその他の技術的な問題。

@Zach Scrivenaが指摘したように、問題をよく特徴付けることで回避できるエラーは、オフバイワンエラーと重複アイテムの処理です。

多くの人は、バイナリ検索を、ソートされた配列から目的の値を見つけるものと見なしています。それが、バイナリ検索自体ではなく、バイナリ方法が使用されている方法です。

私は、二分探索の比較的厳密な定義/定式化を提供しようと試み、 1 つの特定のアプローチに準拠することによって、1 つのエラーと重複する問題を解決する 1 つの方法を示します。これはもちろん新しいものではありません。

# (my) definition of binary search:
input: 
    L: a 'partially sorted' array, 
    key: a function, take item in L as argument
prerequisite: 
    by 'partially sorted' I mean, if apply key function to all item of L, we get a 
    new array of bool, L_1, such that it can't be partitioned to two left, right blocks, 
    with all item in left being false, all item in right being true. 
    (left or/and right could be empty)
output: 
    the index of first item in right block of L_1 (as defined in prerequisite). 
    or equivalently, the index of first item in L such that key(item) == True

この定義により、重複の問題は自然に解決されます。

配列を表すには、一般に [] と [) の 2 つの方法があります。私は後者を好みます。[) と同等のアプローチでは、代わりに (start, count) ペアを使用します。

# Algorithm: binary search
# input: L: a 'partially sorted' array, key: a function, take item in L as argument
    while L is not empty:
        mid = left + (right - left)/2  # or mid = left + count/2
        if key(mid item) is True:
            recede right # if True, recede right
        else:
            forward left # if False, forward left
    return left

このように、「真なら後退（終了）」と「偽なら前進（開始）」の部分を正しく作れば、ほぼ完成です。私はこれを二分探索の「FFTRルール」と呼んでいます。上記の定義のように、最初の項目を検索する場合は左から開始しますが、最後の項目を検索する場合は右から開始します。[) ファッションに準拠している場合、可能な実装は、

while left<right:
    mid = left + (right - left)/2
    if key(L(mid)) == True:
        right = mid
    else:
        left = mid+1
    return left

最初に収束を示し、次に正確性を示して、さらに検証します。

収束：

whenever left == right, we exit loop (also true if being empty at the first)

so, in the loop, if denote, 

    diff = (right - left)/2, 

    lfstep = 1 + diff/2, 'lfstep' for 'left index forward step size'

    rbstep = diff - diff/2, 'rbstep' for 'right index back (recede) step size'

it can be show that lfstep and rbstep are alway positive, so left and right 
will be equal at last. 

both lfstep and rbstep are asymptotically half of current subarray size, so it's 
of logarithm time complexity.

正確さ:

if the input array is empty:
    return the left index;
else:
    if key(mid item) is true:
        "recede right"
        so mid and all item after mid are all true, we can reduce the search range 
        to [left, mid), to validate it, there are two possible cases,
        case 1:
            mid is the first item such that key(item) is True, so there are no true items 
            in new search range [left, mid), so the test will always be false, and we 
            forward left at each iteration until search range is empty, that is  
            [finalleft,mid), since we return finalleft, and finalleft == mid, correctly done!
        case 2:
            there are item before mid such that key(item) is True,
            in this case we just reduce to a new problem of smaller size
    else:
        "forward left"
        mid and all item before mid is false, since we are to find the first true one, 
        we can safely reduce to new search range [mid+1, right) without change the result.

同等の (開始、カウント) バージョン、

while count>0:
    mid = start + count/2
    if key(L[mid]) == True:
        right = mid
    else:
        left = mid+1
return left

要約すると、[) 規則に準拠している場合、 

1. define your key function of your problem, 
2. implement your binary search with "FFTR rule" -- 
    "recede (end) if True ( key(item) == True) else forward (start)" 
    examples:
        if to find a value target, return index or -1 if not found,
        key = lambda x: x>=target, 
        if L[found_index] == target: return found_index
        else: return -1

追加テストによる早期終了については、支払う価値はないと思いますが、試すことはできます。

于 2016-04-23T06:14:38.913 に答える
1

高い値と低い値を合計する 2 つのインデックス間の中間点を計算するときに、整数オーバーフローが発生する可能性があることを考慮しないでください。

参照

于 2009-02-02T18:41:23.547 に答える
0

最新のプロセッサのパイプラインアーキテクチャは、多くの決定と分岐があるバイナリ検索を実行するよりも、線形検索を実行する方がはるかに適しています。

したがって、一般的なパフォーマンスのバグと時期尚早の最適化（これらはすべての悪の根源です）は、単純な線形検索がより高速で、もちろんより単純な場合に、バイナリ検索を使用することです。

読み取りの数によっては、データを並べ替えるだけでも処理が遅くなる可能性があります。線形とバイナリの間の損益分岐点は、単純なキー（32ビット整数など）の場合、簡単に1000要素になる可能性があります。

于 2012-02-24T19:18:08.360 に答える