So verwenden Sie den Interpolationssuchalgorithmus in C++

So verwenden Sie den Interpolationssuchalgorithmus in C++

Einführung:
In vielen Anwendungen müssen wir häufig bestimmte Elemente in geordneten Arrays oder geordneten Datensammlungen suchen und finden. Der herkömmliche binäre Suchalgorithmus ist eine der am häufigsten verwendeten Methoden, in manchen Fällen ist er jedoch möglicherweise nicht effizient genug. Der Interpolationssuchalgorithmus ist ein verbesserter Suchalgorithmus, der das Zielelement basierend auf der Verteilung bekannter Daten schneller finden kann. In diesem Artikel wird erläutert, was der Interpolationssuchalgorithmus ist und wie er in C++ verwendet wird. Außerdem werden Codebeispiele bereitgestellt.

1. Überblick über den Interpolationssuchalgorithmus
   Der Interpolationssuchalgorithmus ist ein Algorithmus, der auf der Grundlage der geschätzten Position des Zielelements in einem geordneten Array oder geordneten Datensatz sucht. Im Gegensatz zum herkömmlichen binären Suchalgorithmus schätzt der Interpolationssuchalgorithmus basierend auf der Verteilung des Zielelements in der Datensammlung, um das Zielelement schneller zu finden. Es verwendet lineare Interpolation, um die Position des Zielelements vorherzusagen, und bestimmt den Suchumfang basierend auf dieser Position. Im Folgenden sind die Schritte des Interpolationssuchalgorithmus aufgeführt:

• Berechnen Sie die geschätzte Position des Zielelements im Datensatz: Berechnen Sie die geschätzte Position basierend auf dem Wert des Zielelements und dem Minimalwert und Maximalwert der Daten festgelegt, und die Array-Länge.
• Bestimmen Sie den Suchbereich: Bestimmen Sie den Suchbereich basierend auf dem geschätzten Standort. Wenn die geschätzte Position kleiner als das Zielelement ist, reicht der Suchbereich von der geschätzten Position bis zum Ende des Datensatzes, andernfalls vom Anfang des Datensatzes bis zur geschätzten Position.
• Binäre Suche innerhalb des Suchbereichs: Verwenden Sie den herkömmlichen binären Suchalgorithmus, um das Zielelement innerhalb des Suchbereichs zu finden.

2. Implementierung des Interpolationssuchalgorithmus in C++
   Lassen Sie uns nun einen Blick darauf werfen, wie der Interpolationssuchalgorithmus in C++ verwendet wird. Zunächst müssen wir eine geordnete Datensammlung bereitstellen und die Funktion des Interpolationssuchalgorithmus implementieren. Das Folgende ist ein einfacher C++-Beispielcode:

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

Im obigen Code definieren wir zunächst eine Funktion mit dem Namen interpolationSearch的函数，它接受一个有序的整数向量arr和目标元素target作为参数。接下来，在函数中我们定义了两个指针low和high，它们表示搜索的范围。然后，我们使用一个循环来进行搜索，直到找到目标元素或搜索范围为空。在循环中，我们首先计算目标元素的预估位置pos，然后检查该位置上的元素是否是目标元素。如果是，我们返回该位置。否则，我们根据目标元素和预估位置的比较结果更新low和high指针的值，缩小搜索范围，直到找到目标元素或搜索范围为空。最后，在主函数中，我们定义了一个有序的整数向量arr和目标元素target，并调用interpolationSearch, um den Interpolationssuchalgorithmus auszuführen. Wenn das Zielelement gefunden wird, drucken wir seine Indexposition aus. Wenn das Zielelement nicht gefunden wird, drucken wir die entsprechenden Eingabeaufforderungsinformationen aus.

3. Fazit
   Der Interpolationssuchalgorithmus ist ein verbesserter Suchalgorithmus, der das Zielelement basierend auf der Verteilung bekannter Daten schnell finden kann. In diesem Artikel wird das Konzept von Interpolationssuchalgorithmen vorgestellt und Codebeispiele für die Implementierung von Interpolationssuchalgorithmen in C++ bereitgestellt. Ich hoffe, dass die Leser durch diesen Artikel die Methode zur Verwendung des Interpolationssuchalgorithmus in C++ beherrschen und ihn in praktischen Anwendungen flexibel einsetzen können.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Interpolationssuchalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!