vendredi 2 juin 2017

What is the role of the (if block) inside the function in the code below?

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