java - ソートされていないデータセットで二分探索を試みるとどうなりますか?

Question

ソートされていないデータセットで二分探索を試みるとどうなりますか?

Answer 1

結果は予測できません。データセットにターゲットがある場合、それが見つかる場合と見つからない場合があります。

EDITキックのために、ちょっとした実験をしました。まず、配列のサイズを選択し、int 配列 {0, 1, ..., size-1} を生成しました。次に、配列をシャッフルし、各値 0、1、...、サイズ 1 に対してバイナリ検索を実行し、見つかった数を数えました。サイズごとに、シャッフル/各値の検索手順を 100,000 回繰り返し、成功した検索の割合を記録しました。(これは、並べ替えられた配列の場合は 100% になります。) 結果は次のとおりです (最も近いパーセントに丸められます)。

Size    % Hit
 10      34%
 20      22%
 30      16%
 40      13%
 50      11%
 60      10%
 70       9%
 80       8%
 90       7%
100       6%

したがって、配列が大きいほど、ソートしないことの影響が悪化します。比較的小さな配列の場合でも、結果はかなり劇的です。

Answer 2

二分探索は、ソートされた配列で機能することを意図しています。ソートされていない配列で実行された場合、結果は確実に予測不能で信頼できなくなります。

Answer 3

二分探索は、ソートされるデータに依存しています。配列内の要素を選択し、決定します 1. これが検索対象の要素である場合 2. 探している要素でない場合、どこで要素を見つけることができるか。

2 番目のポイントは、データの並べ替えに基づいて決定を下します。ソートされていないデータを想像してください。検索キーと選択した要素を比較するだけでは、要素がどこに出現するかを特定することはできません。

そのため、二分探索は、ソートされていないデータでは一貫して機能しません。

Answer 4

探していた要素が見つからないことはほぼ確実です。配列の大部分がソートされている場合は、幸運になる可能性があります。

アルゴリズムは、ある程度の確率でこれを検出する方法で実装できますが、配列の完全なスキャンを行わない限り、二分探索がこのエラー状態を検出することを保証する方法はありません。