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