C++ で補間検索アルゴリズムを使用する方法

C で内挿検索アルゴリズムを使用する方法

はじめに:
多くのアプリケーションでは、順序付けられた配列または順序付けされたデータ セット内で検索する必要があることがよくあります。特定の要素を見つけます。従来の二分探索アルゴリズムは最も一般的に使用される方法の 1 つですが、場合によっては十分な効率が得られない場合があります。補間検索アルゴリズムは、既知のデータの分布に基づいてターゲット要素をより速く見つけることができる改良された検索アルゴリズムです。この記事では、内挿検索アルゴリズムとは何か、およびそれを C で使用する方法をコード例とともに説明します。

1. 補間検索アルゴリズムの概要
   補間検索アルゴリズムは、順序付けされた配列または順序付けされたデータ セット内の対象要素の推定位置に基づいて検索を行うアルゴリズムです。従来の二分探索アルゴリズムとは異なり、補間探索アルゴリズムは、データ コレクション内のターゲット要素の分布に基づいて推定し、ターゲット要素をより速く見つけます。線形補間を使用してターゲット要素の位置を予測し、その位置に基づいて検索範囲を決定します。補間検索アルゴリズムの手順は次のとおりです。

• データ セット内のターゲット要素の推定位置を計算します。ターゲット要素の値と最小値、最大値に基づいて、データセットの値と配列の長さから推定位置を計算します。
• 探索範囲の決定: 推定位置に基づいて探索範囲を決定します。推定位置が対象要素より小さい場合は推定位置からデータセットの末尾まで、それ以外の場合はデータセットの先頭から推定位置までが検索範囲となります。
• 検索範囲内で二分検索を実行する: 従来の二分検索アルゴリズムを使用して、検索範囲内でターゲット要素を検索します。

2. C での補間検索アルゴリズムの実装
   次に、C で補間検索アルゴリズムを使用する方法を見てみましょう。まず、順序付けられたデータのコレクションを提供し、内挿検索アルゴリズムの機能を実装する必要があります。以下は、簡単な C のコード例です。

#include <iostream>
#include <vector>

// 插值搜索算法函数
int interpolationSearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        // 计算预估位置
        int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        
        if (arr[pos] == target) {
            return pos;
        }
        
        if (arr[pos] < target) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
    
    return -1; // 没有找到目标元素
}
 
int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 9;
    
    int result = interpolationSearch(arr, target);
    
    if (result != -1) {
        std::cout << "目标元素 " << target << " 的索引位置为 " << result << std::endl;
    } else {
        std::cout << "目标元素 " << target << " 未找到" << std::endl;
    }
    
    return 0;
}

上記のコードでは、最初に、整数の順序付きベクトルを受け入れる interpolationSearch という名前の関数を定義しますarr およびターゲット要素 target をパラメーターとして使用します。次に、関数内で、検索範囲を表す 2 つのポインター low と high を定義します。次に、ループを使用して、目的の要素が見つかるか、検索範囲が空になるまで検索します。ループ内では、まず対象要素の推定位置 pos を計算し、その位置の要素が対象要素であるかどうかを確認します。そうであれば、その場所を返します。それ以外の場合は、対象要素と推定位置との比較結果に基づいて low および high ポインタの値を更新し、対象要素が見つかるまで検索範囲を絞ります。見つかったか、検索範囲が空です。最後に、main 関数で、順序付き整数ベクトル arr とターゲット要素 target を定義し、interpolationSearch 関数を呼び出して内挿検索アルゴリズムを実行します。ターゲット要素が見つかった場合は、そのインデックス位置を出力し、ターゲット要素が見つからなかった場合は、対応するプロンプト情報を出力します。

3. 結論
   補間検索アルゴリズムは、既知のデータの分布に基づいてターゲット要素を迅速に見つけることができる、改良された検索アルゴリズムです。この記事では、内挿検索アルゴリズムの概念を紹介し、C で内挿検索アルゴリズムを実装するコード例を示します。読者の皆様がこの記事を通じてC言語での内挿探索アルゴリズムの使い方をマスターし、実践で柔軟に使いこなせるようになれば幸いです。

以上がC++ で補間検索アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。