gistfile1.txt

#include <iostream>
#include <cmath>
using namespace std;

int BinarySearch(int L[], int left, int right, int key){

    if(right - left > 0){

        int mid = (left + right) / 2;

        if(key > L[mid]){

            BinarySearch(L, mid + 1, right, key);

        } else if(key < L[mid]){

            BinarySearch(L, left, mid, key);

        } else {

            return mid;

        }

    } else {

        return -1;

    }

}

int ExponentialSearch(int L[], int left, int right, int key)
{

    if(right - left <= 0){
        return -1;
    }

    int i = 1;

    while(i < right - left){

        if(L[i] < key){

            i = (i * 2);

        } else {

            break;

        }

    }

    return BinarySearch(L, i/2, i, key);

}

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 = -1;

    int x;
    if((x = ExponentialSearch(L, left, right, key)) == -1 ){

        cout << "Key doesn't exist"<< endl;

    } else {

        cout << "The position of Key is " << x << endl;

    }

return 0; }