C++で単一連結リストに対する二分探索を実装する方法

単一連結リスト（片方向リンクリスト）とは、各ノードが「値」と「次のノードのメモリ位置」を保持するデータ構造であり、一方向にしかたどることができない連結リストのことです。

二分探索（バイナリサーチ）は、分割統治法に基づく探索アルゴリズムです。データ構造の中央要素を取り出して探索対象の値と比較し、一致しなければ、同じアルゴリズムを上半分または下半分に再帰的に適用しながら探索範囲を絞り込んでいきます。

ここでは、単一連結リストと探索対象の値が与えられ、二分探索によってその値を検索します。

単一連結リストはポインタを1つしか持たないデータ構造のため、中央の要素を直接取得するのは容易ではありません。そこで、中央位置の取得には「slow / fast」の2ポインタ方式を利用します。

アルゴリズム

ステップ1 : start_node（リストの先頭）、last_node（末尾側の境界ノード）、mid_node（中央ノード）を初期化する。
ステップ2 : mid_nodeと探索値を比較する
　ステップ2.1 : mid_node = 探索値 の場合、「見つかった」を返す。
　ステップ2.2 : mid_node > 探索値 の場合、下半分に対して二分探索を呼び出す。
　ステップ2.3 : mid_node < 探索値 の場合、上半分に対して二分探索を呼び出す。
ステップ3 : リスト全体を走査しても見つからなければ、「見つからない」を返す。

実装例（C++）

以下はC++による実装例です。mid_node関数で2ポインタを用いて中央ノードを求め、binarySearch関数で探索範囲を半分ずつ絞り込みながら値を検索しています。なお、二分探索を正しく機能させるには、リストがソート済みである必要があります。

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node* next;
};
Node *newNode(int x){
    struct Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}
struct Node* mid_node(Node* start, Node* last){
    if (start == NULL)
        return NULL;
    struct Node* slow = start;
    struct Node* fast = start -> next;
    while (fast != last){
        fast = fast -> next;
        if (fast != last){
            slow = slow -> next;
            fast = fast -> next;
        }
    }
    return slow;
}
struct Node* binarySearch(Node *head, int value){
    struct Node* start = head;
    struct Node* last = NULL;
    do{
        Node* mid = mid_node(start, last);
        if (mid == NULL)
            return NULL;
        if (mid -> data == value)
            return mid;
        else if (mid -> data < value)
            start = mid -> next;
        else
            last = mid;
    }
    while (last == NULL || last != start);
        return NULL;
}
int main(){
    Node *head = newNode(54);
    head->next = newNode(12);
    head->next->next = newNode(18);
    head->next->next->next = newNode(23);
    head->next->next->next->next = newNode(52);
    head->next->next->next->next->next = newNode(76);
    int value = 52;
    if (binarySearch(head, value) == NULL)
        printf("Value is not present in linked list\n");
    else
        printf("The value is present in linked list\n");
    return 0;
}

出力

The value is present in linked list

実行結果は「リストに値が存在します」という意味です。

ポイント解説

• mid_node関数：slowポインタは1つずつ、fastポインタは2つずつ進めることで、fastが末尾に到達したときにslowが中央に位置します。
• binarySearch関数：中央の値が探索値より小さければ探索開始位置を中央の次のノードへ、大きければ末尾境界を中央へ移動し、探索範囲を半分に絞り込みます。
• 計算量：連結リストはランダムアクセスができず、中央ノードの取得にO(n)かかるため、全体の計算量はO(n log n)になります。配列に対する二分探索（O(log n)）に比べると非効率である点に注意しましょう。