三分探索（Ternary Search）とは？仕組み・計算量・C++実装例をわかりやすく解説

三分探索（Ternary Search）とは

三分探索は、二分探索と同じ考え方に基づいた探索アルゴリズムで、リストを部分リストに分割しながら目的のキー値を探します。二分探索がリストを2つに分割するのに対し、三分探索では2つの中間値（mid）を使ってリストを3つの部分に分割します。分割数を増やすことで探索範囲がより早く狭まり、キー値の探索にかかる時間を短縮できます。

三分探索の計算量

• 時間計算量：O(log₃ n)
• 空間計算量：O(1)

入力と出力

入力：
ソート済みのデータリスト：12 25 48 52 67 79 88 93
探索キー：52

出力：
要素は位置 3 で見つかりました

アルゴリズム

ternarySearch(array, start, end, key)

入力：ソート済みの配列、探索範囲の開始位置と終了位置、探索キー

出力：キーが見つかった場合はその位置、見つからない場合は無効な位置

擬似コード

Begin
    if start <= end then
        midFirst := start + (end - start) / 3
        midSecond := midFirst + (end - start) / 3
        if array[midFirst] = key then
            return midFirst
        if array[midSecond] = key then
            return midSecond
        if key < array[midFirst] then
            call ternarySearch(array, start, midFirst - 1, key)
        if key > array[midSecond] then
            call ternarySearch(array, midSecond + 1, end, key)
        else
            call ternarySearch(array, midFirst + 1, midSecond - 1, key)
    else
        return invalid location
End

処理の流れ

1. 探索範囲の先頭を start、末尾を end とします。
2. midFirst = start + (end − start) / 3、midSecond = midFirst + (end − start) / 3 として、2つの中間位置を求めます。
3. array[midFirst] または array[midSecond] がキーと一致すれば、その位置を返します。
4. キーが array[midFirst] より小さい場合は左側の区間 [start, midFirst−1] を、キーが array[midSecond] より大きい場合は右側の区間 [midSecond+1, end] を再帰的に探索します。
5. いずれにも当てはまらない場合は、中央の区間 [midFirst+1, midSecond−1] を探索します。
6. start が end を超えたら、キーはリスト内に存在しないとして終了します。

C++による実装例

#include<iostream>
using namespace std;

int ternarySearch(int array[], int start, int end, int key) {
    if(start <= end) {
        int midFirst = start + (end - start) / 3;      // 第1区間と第2区間の境界
        int midSecond = midFirst + (end - start) / 3;  // 第2区間と第3区間の境界
        if(array[midFirst] == key)
            return midFirst;
        if(array[midSecond] == key)
            return midSecond;
        if(key < array[midFirst])
            return ternarySearch(array, start, midFirst - 1, key);
        if(key > array[midSecond])
            return ternarySearch(array, midSecond + 1, end, key);
        return ternarySearch(array, midFirst + 1, midSecond - 1, key);
    }
    return -1;
}

int main() {
    int n, searchKey, loc;
    cout << "要素数を入力してください: ";
    cin >> n;
    int arr[n];  // サイズ n の配列を作成
    cout << "要素を入力してください: " << endl;

    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "探索するキーを入力してください: ";
    cin >> searchKey;
    if((loc = ternarySearch(arr, 0, n - 1, searchKey)) >= 0)
        cout << "要素は位置 " << loc << " で見つかりました" << endl;
    else
        cout << "要素はリスト内に見つかりませんでした。" << endl;
}

実行結果

要素数を入力してください: 8
要素を入力してください:
12 25 48 52 67 79 88 93
探索するキーを入力してください: 52
要素は位置 3 で見つかりました

まとめ

三分探索は、リストを3分割しながら探索範囲を絞り込んでいくシンプルな再帰アルゴリズムです。時間計算量は O(log₃ n) で、理論上は二分探索の O(log₂ n) よりも反復回数を抑えられます。ただし、1回の反復あたりの比較回数が二分探索より多いため、実際の処理速度は二分探索と同等かそれ以下になることも多い点には注意が必要です。ソート済みの配列から目的の値を高速に見つけたい場合の選択肢のひとつとして、仕組みを理解しておくと良いでしょう。