How to use interpolation search algorithm in C++

How to use the interpolation search algorithm in C

Introduction:
In many applications, we often need to search in ordered arrays or ordered data sets Conduct searches and find specific elements. The traditional binary search algorithm is one of the most commonly used methods, but in some cases, it may not be efficient enough. The interpolation search algorithm is an improved search algorithm that can find the target element faster based on the distribution of known data. This article explains what the interpolation search algorithm is and how to use it in C, along with code examples.

1. Overview of interpolation search algorithm
   The interpolation search algorithm is an algorithm that searches based on the estimated position of the target element in an ordered array or ordered data set. Different from the traditional binary search algorithm, the interpolation search algorithm estimates based on the distribution of the target element in the data collection to find the target element faster. It uses linear interpolation to predict the position of the target element and determines the scope of the search based on that position. The following are the steps of the interpolation search algorithm:

• Calculate the estimated position of the target element in the data set: based on the value of the target element and the minimum value, maximum value of the data set, and the array length. Calculate estimated location.
• Determine the search range: Determine the search range based on the estimated location. If the estimated position is smaller than the target element, the search range is from the estimated position to the end of the data set; otherwise, it is from the beginning of the data set to the estimated position.
• Perform binary search within the search range: Use the traditional binary search algorithm to find the target element within the search range.

2. Implementation of interpolation search algorithm in C
   Now let’s take a look at how to use the interpolation search algorithm in C. First, we need to provide an ordered collection of data and implement the function of the interpolation search algorithm. The following is a simple C example code:

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

In the above code, we first define a function named interpolationSearch, which accepts an ordered vector of integersarr and target element target as parameters. Next, in the function we define two pointers low and high, which represent the search range. We then use a loop to search until the target element is found or the search range is empty. In the loop, we first calculate the estimated position pos of the target element, and then check whether the element at that position is the target element. If so, we return that location. Otherwise, we update the values ​​of the low and high pointers based on the comparison results between the target element and the estimated position, and narrow the search range until the target element is found or the search range is empty. Finally, in the main function, we define an ordered integer vector arr and the target element target, and call the interpolationSearch function to perform the interpolation search algorithm. If the target element is found, we print out its index position; if the target element is not found, we print out the corresponding prompt information.

3. Conclusion
   The interpolation search algorithm is an improved search algorithm that can quickly find the target element based on the distribution of known data. This article introduces the concept of interpolation search algorithms and provides code examples that implement interpolation search algorithms in C. I hope that readers can master the method of using the interpolation search algorithm in C through this article, and can use it flexibly in practical applications.

The above is the detailed content of How to use interpolation search algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!