This is an interpolation search which I found in an YouTube video but without sound. I have understood most of the part in the code but why do I need to use the if(key == arr[low])?
if (key == arr[low]){
return low ;
} else {
return -1;
}
The whole program is down below.
#include <iostream>
#include <cmath>
using namespace std;
int z = 0;
int interpolation(int arr[], int left, int right, int key){
int low = left;
int high = right - 1;
int mid;
while (arr[high] != arr[low] && key >= arr[low] && key <= arr[high]) {
mid = low + ( (key - arr[low]) * (high - low) / (arr[high] - arr[low]) );
if (key > arr[mid]){
low = mid + 1;
} else if (key < arr[mid]){
high = mid - 1;
} else{
return mid;
}
}
if (key == arr[low]){
return low ;
} else {
return -1;
}
}
int main()
{
int L[] = {0, 1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
//int L[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int left = 0;
int right = sizeof(L) / sizeof(L[0]);
int key = 6;
int x;
if((x = interpolation(L, left, right, key)) == -1 ){
cout << "Key doesn't exist"<< endl;
} else {
cout << "The position of Key is " << x << endl;
}
return 0; }
Without this part, some of the index does not work. However, isn't the else inside the while loop covering the whole thing?
else{
return mid;
}
Thank you.
Aucun commentaire:
Enregistrer un commentaire