#include <iostream>
using namespace std;


int binarySearch_recursive(int a[],int key,int left,int right){
int range = right - left;
int i = left + range/2;
if (range < 2)
return -1;
else if (key == a[i])
return i;
else if (key < a[i])
return binarySearch_recursive(a,key,left,i);
else if (key > a[i])
return binarySearch_recursive(a,key,i,right);
}

int binarySearch_iterative(int a[],int key,int left,int right){
while (right - left > 1){
int range = right - left;
int i = left + range/2;
if (key == a[i])
return i;
else if (key < a[i])
right = i;
else if (key > a[i])
left = i;
}
return -1;
}

int main(){
int a[] = {1,2,3,4,5,6,7,8,9,10};
cout << binarySearch_recursive(a,4,0,9) << endl;
cout << binarySearch_iterative(a,8,0,9) << endl;
system("pause");

}