algorithm - ソートされていない配列の二分探索？

Question

私はこのドキュメントに出くわしました。バイナリ検索は、ソートされていない配列（リスト）にもバイナリ検索を使用できることを著者が証明/説明したところです。私は最初の読書で文書の多くをざわめきませんでした。

すでにこれを調べた人はいますか？

Answer 1

紙を読んだところです。私にとって、著者はバイナリ検索という用語を使用して、連続関数のゼロを見つけるために使用される二分法に対処しています。

この論文の例は、間隔内のゼロを見つける (y 軸の変換を使用) や、表形式データの関数の最大/最小を見つけるなどの問題に明確に触発されています。

エッセイで考慮される配列は、ランダムに埋められたものではありません。それらを構築するためのルールが見つかります (これは、それらをダンプするために使用される関数に関連付けられたルールです)。

類似点と相違点を見つけるために、共通のファミリーに属するさまざまなアルゴリズムをいじる良い機会であると述べました。経験を広げる良い機会です。

新しい概念でも、過小評価された概念でもないことは間違いありません。

Answer 2

バイナリまたは二分法を使用して、ソートされていないリストから 3 を探します。

L = 1 5 2 9 38 11 3

1-リスト全体の中間点をとる L : 9 3 < 9 なので、リストの右側の部分 (38 11 3) を削除します。

2-残りのリストの中間点を取る 1 5 2 : 5 3 > 5 したがって、リストの右側の部分を削除 (5 2) は 1 のまま

結果 : 3 件の未検出

2 つの注意事項:

1-バイナリまたは二分アルゴリズムは、右と左を順序の指標と見なします。したがって、右が高く、左が低いと見なして、通常のアルゴリズムを無作法に適用しました。反対を考慮する場合、つまり、右が低く、左が高い場合、このわずかに似たリストで 3 を見つけようとすると、「 3 unfound 」につながります L' = L = 1 5 2 9 3 38 11 3 < 9 / 右部分を取得 : 3 38 11 中間点 38 3 < 38 右部分を取得 : 11 3 不明

2-リストの削除された部分にアルゴリズムを体系的に再適用することを受け入れる場合、n個の要素のリスト内の要素を検索することにつながる複雑さは、最初から最後まですべてのリストを実行するのとまったく同じO(n)になりますあなたの価値を探ります。検索時間が少し短くなる可能性があります。なんで ？あなたが最初から1つずつ見て考えてみましょう。ソートされたリストの値 100000 で終了します。あなたのリストの最後にあります！:-)

このリストが順序付けられておらず、値 100000 がたとえばちょうど中間点にある場合...ビンゴ!!

Answer 3

二分探索は、ローテーションされたソートされていない配列/リストに実装できます。