Comment utiliser l'algorithme de recherche par interpolation en C++

Comment utiliser l'algorithme de recherche par interpolation en C++

Introduction :
Dans de nombreuses applications, nous devons souvent rechercher et trouver des éléments spécifiques dans des tableaux ordonnés ou des collections de données ordonnées. L’algorithme de recherche binaire traditionnel est l’une des méthodes les plus couramment utilisées, mais dans certains cas, il peut ne pas être suffisamment efficace. L'algorithme de recherche par interpolation est un algorithme de recherche amélioré qui peut trouver l'élément cible plus rapidement en fonction de la distribution des données connues. Cet article présentera ce qu'est l'algorithme de recherche par interpolation et comment l'utiliser en C++, et fournira des exemples de code.

1. Présentation de l'algorithme de recherche par interpolation
   L'algorithme de recherche par interpolation est un algorithme qui recherche en fonction de la position estimée de l'élément cible dans un tableau ordonné ou un ensemble de données ordonné. Différent de l'algorithme de recherche binaire traditionnel, l'algorithme de recherche par interpolation estime en fonction de la distribution de l'élément cible dans la collecte de données pour trouver l'élément cible plus rapidement. Il utilise l'interpolation linéaire pour prédire la position de l'élément cible et détermine la portée de la recherche en fonction de cette position. Voici les étapes de l'algorithme de recherche par interpolation :

• Calculer la position estimée de l'élément cible dans l'ensemble de données : Calculer la position estimée en fonction de la valeur de l'élément cible et de la valeur minimale, valeur maximale des données défini et la longueur du tableau.
• Déterminez la plage de recherche : déterminez la plage de recherche en fonction de l'emplacement estimé. Si la position estimée est plus petite que l'élément cible, la plage de recherche s'étend de la position estimée à la fin de l'ensemble de données, sinon elle s'étend du début de l'ensemble de données à la position estimée ;
• Recherche binaire dans la plage de recherche : utilisez l'algorithme de recherche binaire traditionnel pour trouver l'élément cible dans la plage de recherche.

2. Implémentation de l'algorithme de recherche par interpolation en C++
   Voyons maintenant comment utiliser l'algorithme de recherche par interpolation en C++. Tout d’abord, nous devons fournir une collection ordonnée de données et implémenter la fonction de l’algorithme de recherche par interpolation. Ce qui suit est un exemple de code C++ simple :

#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;
}

Dans le code ci-dessus, nous définissons d'abord une fonction nommée interpolationSearch的函数，它接受一个有序的整数向量arr和目标元素target作为参数。接下来，在函数中我们定义了两个指针low和high，它们表示搜索的范围。然后，我们使用一个循环来进行搜索，直到找到目标元素或搜索范围为空。在循环中，我们首先计算目标元素的预估位置pos，然后检查该位置上的元素是否是目标元素。如果是，我们返回该位置。否则，我们根据目标元素和预估位置的比较结果更新low和high指针的值，缩小搜索范围，直到找到目标元素或搜索范围为空。最后，在主函数中，我们定义了一个有序的整数向量arr和目标元素target，并调用interpolationSearch pour effectuer l'algorithme de recherche d'interpolation. Si l'élément cible est trouvé, nous imprimons sa position d'index ; si l'élément cible n'est pas trouvé, nous imprimons les informations d'invite correspondantes.

3. Conclusion
   L'algorithme de recherche par interpolation est un algorithme de recherche amélioré qui peut trouver rapidement l'élément cible en fonction de la distribution des données connues. Cet article présente le concept d'algorithmes de recherche par interpolation et fournit des exemples de code pour implémenter des algorithmes de recherche par interpolation en C++. J'espère que les lecteurs pourront maîtriser la méthode d'utilisation de l'algorithme de recherche par interpolation en C++ grâce à cet article et pourront l'utiliser de manière flexible dans des applications pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!