// recursive binary search

#include <iostream.h>
#include <stdio.h>
#include <math.h>


int BinarySearch(int a[], int key, int left, int right)
{
//	if (left > right)  return -1;                          // unsuccessful search 

	int m = (int) floor( (double) (left + right)/2 );

	if (a[m] == key)  return m;                            // found at location m
	else  
	{
		  if (key < a[m]  && left < m)  return BinarySearch(a, key, left, m-1);
		  else  
		  {
			  if (key > a[m]  &&  right > m)  return BinarySearch(a, key, m+1, right);
			  else  return -1;                             // not found
		  }
	}
}


void main(void)
{
	int L[10] = {0,1,   12,13,14,15,16,17,     8,9};
	int position;

	if ( (position = BinarySearch(L, 12, 2, 7)) == -1) cout << "not found" << endl;
	else cout << "found at position " << position << endl;

	getchar();
}