この以前の質問では、O(n) 時間で二重リンク リストに対してバイナリ検索を行うことについて説明しています。その回答のアルゴリズムは次のように機能します。
これは、前方と後方の両方に移動できるため、双方向にリンクされたリストでは完全に機能しますが、このアルゴリズムは片方向にリンクされたリストでは機能しません。
二重リンクリストではなく片リンクリストでバイナリ検索を時間 O(n) で機能させることは可能ですか?
これを機能させることは絶対に可能です。実際、二重リンク リスト アルゴリズムを機能させるために必要な変更はほとんど 1 つだけです。
片方向リストの場合の問題は、リストの中央へのポインターがある場合、リストの最初の 4 分の 1 に戻るために逆戻りできないことです。しかし、考えてみれば、これを行うために途中から始める必要はありません。代わりに、リストの先頭から始めて、第 1 四半期まで歩くことができます。これには（基本的に）以前と同じ時間がかかります。n / 4 ステップ後退するのではなく、前方から開始して n / 4 ステップ前進することができます。
ここで、最初のステップを完了し、位置 n / 4 または 3n / 4 にいるとします。この場合、位置 n / 8 または位置 5n に戻る必要がある場合、以前と同じ問題が発生します。 / 8. n / 8 の位置に移動する必要がある場合は、リストの先頭から再び n / 8 歩進むことができます。5n/8の場合は？ここにトリックがあります - n / 2 ポイントへのポインターがまだある場合は、そこから開始して n / 8 歩進むと、正しい場所に移動できます。
より一般的には、リストの中央へのポインターを格納する代わりに、リストに2 つのポインターを格納します。リストを前方に進める必要がある場合は、範囲の開始点へのポインターを範囲の中央へのポインターに更新してから、範囲の中央へのポインターを範囲の終了点の途中まで進めます。リストを後方に進める必要がある場合は、範囲の中央へのポインタを範囲の先頭へのポインタに更新してから、途中まで進みます。
全体として、これは二重にリンクされたケースとまったく同じ時間の複雑さを持ちます: n / 2 ステップ、次に n / 4 ステップ、次に n / 8 ステップ、など、合計で O(n) ステップになります。また、O(log n) の合計比較のみを行います。唯一の違いは、追跡する必要がある追加のポインターです。
お役に立てれば！
比較には O(1) かかり、さらに時間がかかるのはノードのトラバースです。したがって、n/2、n/4、および 3n/4 へのポインターを保持していても、それを見つけるのにかかる時間は O(n) のままです。
さらに、途中から開始して戻る（または進む）場合は、別の比較を行うのに同じ時間がかかるため、途中で比較することもできます：O（1）。
要約する
と、O(1) 内の要素への直接アクセスを許可する配列 (ArrayList) によって連結リストがバックアップされていない限り、連結リストでバイナリ検索を実行しても意味がありません。
これは、この調査作業で説明されているように、ダブル ポインター メソッド (リストが並べ替えられている場合) を使用することで実現できます。