リンクリストにバイナリ検索を適用して要素を見つけることは可能ですか？

Question

質問を読んだことがありますか？リンクリストにバイナリ検索を適用できますか？

リンクリストではランダムアクセスが許可されていないため、実際には不可能です。

いずれかの方法がありますか？

Answer 1

リンクリストのランダムアクセスはO（n）なので、プレーンリンクリストではバイナリ検索を直接行うことはできません。

高速検索が必要な場合は、ツリー形式のデータ構造（R/Bツリー、トライ、ヒープなど）を使用すると、リンクされたリストの多くの利点（比較的安価なランダム挿入/削除）効率的な検索。

Answer 2

あなたが述べた理由から、古典的なリンクリストではありません。

しかし、リンクリストから派生したバイナリ検索の形式を可能にする構造があります：Skip lists。

（これは、実装が容易ではありません。）

Answer 3

主な問題、あなたはリンクリスト要素への一定時間アクセスがないこと以外は、あなたがリストの長さについての情報を持っていないということです。この場合、2つの半分でリストを「切り取る」方法がありません。

少なくともリンクリストの長さにバインドされている場合、問題はO（log n）で解決できます。スキップリストアプローチです。さもなければ、何もあなたをリスト全体、従ってO（n）を読むことから救いません。

リンクリストがソートされており、その長さ（または少なくとも最大長）がわかっているとすると、リンクリストに何らかの種類のバイナリ検索を実装することができます。しかし、これはよくあるケースではありません。

Answer 4

ソートされたキーを含む1つのリンクされたリストのようなものを実装しました。私はその中にいくつかのキーを見つける必要があった（最初はそれらのうちの1つしか知りませんでした、残りはそれに依存していました）。そして私はリストの長さを知らなかった。

私はこれをやり終えました...リスト要素を指すポインタを256個作成し、最初の256個のリスト要素を指し示しました。すべての256が使用され、257が必要になるとすぐに、私は奇数番号のポインタ値（1,3,5など）を落とし、偶数番号（0,2,4など）を最初の128個のポインタに圧縮しました残りの半分（128）のポインタを残りの部分に割り当て続け、今回は他のすべてのリスト要素をスキップします。このプロセスは、リストの終わりまで繰り返され、その時点で、それらのポインタは、リスト全体にわたって均等に配置された要素を指していた。私はその後、元のリストの長さの1/256（または1 /何であれ）まで線形リスト検索を短縮するために、それらの256個（またはそれ以下）のポインタを使って単純な2分探索を行うことができました。

これはあまりファンシーでもパワフルでもありませんが、マイナーコードの変更で十分なパフォーマンス改善が得られることがあります。

Answer 5

リンクリストでバイナリ検索を実行できます。あなたが言うように、あなたはランダムアクセスを持っていませんが、特定のインデックスを持つ要素を見つけることができます。リストの先頭か他の位置から開始します。したがって、簡単なバイナリ検索は可能ですが、配列のバイナリ検索と比較して遅いです。

単純なリストのトラバーサルよりもはるかに高価なリストがあった場合、バイナリ検索は、適切なサイズのリストの線形検索より安くなります。リニア検索では、O(n)の比較とO(n)のノードトラバーサルが必要ですが、バイナリ検索では、O(log n)の比較とO(n log n)のノードトラバーサルが必要です。そのO(n log n)が縛られているかどうかは分かりません。

Answer 6

私によれば、リンクリストをバイナリ検索の方法で検索する方法はありません。バイナリ検索では、リストでは不可能な配列の 'mid'値を見つけるのが普通です。なぜなら、リストは厳密に 'start'（リストの最初のノードを指すノード）を使用して、私たちのリスト要素。

配列では、INDEXを使用して特定の要素に移動することができます。ここでは、Index（リンクリストのランダムアクセスが利用できないために）の質問はありません。

したがって、通常の方法でリンクリストではバイナリ検索ができないと思います。