Data structure experiment – implementing interpolation and Fibonacci search

Among them, k is a given value, elem[low] and elem[high] are the data elements with the minimum keyword and the maximum keyword in the search interval respectively, which are at both ends of the search interval. The interpolation algorithm improves the proportion parameter of the half search to be adaptive based on the position of the keyword in the entire ordered list, so that the change of the mid value is closer to the keyword key.

2. Fibonacci search

Fibonacci search is also a search method based on a word table that gradually narrows the search interval. The method’s search interval endpoints and midpoints are related to the Fibonacci sequence. The Fibonacci sequence is defined as: 1, 1, 2, 3, 5, 8, 13,…. That is, valence 1)=1, f(2)=1, fi)=fi-l) + f(i-2) (when i>2).

The concept of Fibonacci search: keep mid at the golden section point of the array. The length of the front of mid is F[K-1]-1, the length of the back is F[K-2]-1, and the total length of the array is F[ K]-1, mid is at the golden section point.

1.2 Description of file structure, development environment, etc.

1.3 Implementation Technology

1. Interpolation search algorithm

The elem[] array stores n pieces of data in an ordered list, and the n data elements are arranged from small to large according to their keywords. And at the beginning, set the lower limit of the search interval low-0 and the upper limit high=n-1. If low>high, it means that the search failed and -1 is returned: otherwise, it enters the while loop to search. First find the data element subscript mid = low + (high – low) * (k – elem[low]) / (elem[high] – elem[low]) at the search interval division, and use the keyword of the data element elem[mid] is compared with the given value key, and the comparison result is passed through multiple if-else judgment statements:

①If elem[mid]==key, the search is successful, the success information is reported and its subscript mid is returned

②If elem[mid]

③If elem[mid]>key, it means that if the data element you are looking for exists in the data table, the data element must be on the left side of mid. You can narrow the search interval to the first half of the data table (high=mid-1) and then continue the search.

template<class ElemType>
int InsertSearch(ElemType elem[], int n, ElemType key, int & amp;count3)
// Operation result: Iterative algorithm, search for the element whose key value is equal to key in the ordered list. If the search is successful, the serial number of this element will be returned, otherwise -1 will be returned.
{
int low = 0, high = n - 1;int mid;
while (low <= high)
{
count3 + + ;
if (elem[high] - elem[low] != 0)
mid = low + (high - low) * (key - elem[low]) / (elem[high] - elem[low]);
else
return -1;
if (key == elem[mid])
{
count3 + + ;
return mid;
}
else if (key <= elem[mid])
{
high = mid - 1;
count3 + + ;
}
else
{
low = mid + 1;
count3 + + ;
}
}
return -1;
}

2、Fibonacci Algorithm

The elem[] array stores n pieces of data in an ordered list, and the n data elements are arranged from small to large according to their keywords. And at the beginning, set the lower limit of the search interval low-0 and the upper limit high=n-1. Use a for loop to generate the Fibonacci sequence and store it in the fib[] array. The while loop finds the closest maximum sequence value of the number of elements in the ordered list in the Fibonacci sequence, and if n does not satisfy the value of an element in the Fibonacci sequence, use elem[high] to complete the order Table, the algorithm idea behind is similar to the binary search:

1) If the length of the search interval is less than (low>high), the search fails and -1 is returned: otherwise, continue with the following steps.

2) Find the data element subscript mid=f(k-1)-1 at a certain position in the search interval based on the Fibonacci sequence

3) The keyword elem[mid] of the data element in the middle of the interval is compared with the given value key. The comparison results have the following three possibilities.

①If elem[mid]==key, the search is successful, the success information is reported and its subscript mid is returned

② If elem[mid]

③If elem[mid]>key, it means that if the data element you are looking for exists in the data table, the data element must be on the left side of mid. The search interval can be reduced to the first half of the data table, and the length of the obtained subtable is exactly f(k-1)-1, and then the Fibonacci search can be continued.

//Fibonacci search
template<class ElemType>
int FibonacciSearch(ElemType elem[], int n, ElemType key, int & amp;count2)
{
int low = 0, high = n - 1;
int mid, fib[MAXSIZE], k = 0;
fib[0] = fib[1] = 1;
for (int i = 2; i < MAXSIZE; i + + )
fib[i] = fib[i - 1] + fib[i - 2];
//Find the closest maximum sequence value to the number of elements in the ordered list in the Fibonacci sequence
while (high > fib[k] - 1)
k++;
//Complete the ordered list
for (int i = n; i <= fib[k] - 1; i + + )
elem[i] = elem[high];
while (low <= high)
{
count2 + + ;
mid = low + fib[k - 1] - 1;//Golden section based on Fibonacci sequence
if (key == elem[mid])
{
count2 + + ;
if (mid <= n - 1)
{
count2 + + ;
return mid;
}
else//Indicates that the obtained data element is a completion value
{
return n - 1;
count2 + + ;
}
}
if (elem[mid] > key)
{
count2 + + ;
high = mid - 1;
k = k - 1;
}
if (elem[mid] < key)
{
count2 + + ;
low = mid + 1;
k = k - 2;
}
}
return -1;
}

1.4Test results

1. The number n of ordered table data is large and the distribution is relatively even – interpolation search

elem[10000] = {1,2,3,4,5,6,7,8,9,……,9993,9994,9995,9996,9997,9998,9999,10000}

key=5

int elem[10000];
for (int i = 0; i < 10000; i + + )
elem[i] = i + 1;
int k = 5;

Test Results:

The number of comparisons of interpolation search is significantly less than that of binary search and Fibonacci search, which shows that interpolation search is more appropriate when the number of data elements in an ordered list is large and the distribution is relatively uniform.

2. The number n of ordered table data is large, and the distribution is extreme and uneven – Fibonacci search/half search

for (int i = 0; i < 10; i + + )
elem[i] = i + 1;
for (int i = 10; i < 100; i + + )
elem[i] = i + 1990;
for (int i = 100; i < 1500; i + + )
elem[i] = i + 98999;
int k = 98943;