#include <iostream>
#include <iomanip>

using namespace std;

// binary search prototype
int binarySearch( int a[], int first, int last, int key, int count );

int main()
{
	const int size = 18;
	int arr[size] = { 1, 2, 5, 7, 9, 12, 13, 17, 19, 20, 25, 48, 56, 78, 81, 89, 93, 96};
	int searchkey = 0;
		
	// Displays the sorted array list
	for ( int i = 0; i < size; i++ )
	{
		cout << setw(4) << arr[i];
		if ( (i + 1) % 5 == 0 ) cout << endl;
	}
	
	// prompts the user to enter a value
	while ( searchkey != -1 )
	{
		cout << "\nEnter a search key (-1 to quit): ";
		cin >> searchkey;
		if ( searchkey == -1 ) break;
		
		// displays results
		int repetitions = binarySearch( arr, arr[0], size, searchkey, 0 );
			cout << "The key has been found after "<<repetitions<<" repetitions\n"; 	
	}

	return 0;
}

// RECURSIVE BINARY SEARCH FUNCTION
int binarySearch( int a[], int first, int last, int key, int count )
{
		int middle = (first + last) / 2;

		if ( key == a[middle] )
		{
			return count;
		}
		else if ( key < a[middle] )
		{
			count +=1;
			return binarySearch( a, first, middle-1, key, count );
		}
		
		else if ( key > a[middle] )
		{
			return binarySearch( a, middle+1, last, key, count );
			count +=1;
		}
		
	return -1;
}