//Recursive Binary Search Program

#include<iostream.h>
#include<time.h>
#include<stdio.h>
const int SIZE = 14;
void search(const int a[], int first, int last, int key,
				  int &found, int &location);
int main()
{  int a[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 20};
   const int final_index = SIZE - 1;
   int key, location, found;
   double x,y,z;   //clock variables  

  // set the time of processing at the beginning of the program
   x = clock();
   
  // begin the binary search program

   cout << "Enter a number to be located: ";
   cin >> key;
   search(a, 0, final_index, key, found, location);
   
   if (found)
      cout << key << " is in index location " << location << endl;
   else
      cout << key << " is not in the array." << endl;
     
  // set the time of processing at the end of the program
   y = clock();   
   z = (y - x)/CLOCKS_PER_SEC;
 //  cout << "The execution time of this program is: " << z << endl;

   printf("The execution time is: %.15lf\n\n", z); //Format 15 decimal places 
   return 0;
}

void search(const int a[], int first, int last, int key,
					int &found, int &location)
{
   int mid;
   if (first > last)
      found = 0;
   else
   {  mid = (first + last)/2;
      if (key == a[mid])
       {
	  found = 1;
	  location = mid;
       }
      else if (key < a[mid])
      {
	 search(a, first, mid - 1, key, found, location);
      }
      else if (key > a[mid])
       {
	  search(a, mid + 1, last, key, found, location);
       }
      }
}