// Program to implement binary search recursively.
// Assignment-13
// bnsrch.cpp, Author - Krishna Kumar Khatri.

// Uncomment ONLY the following line if you are using Turbo/Borland compiler.
// #define TC
#ifdef TC
	#include <iostream.h>
	#include <string.h>
#else
	#include <iostream>
	#include <cstring>
	using namespace std;
#endif
#include <conio.h>  // For getch.

void swap(int& a, int& b)
    { a = a - b; b = a + b; a = b - a; }

void sort(int arr[], const int& arrsize)
{
    int i, j;
    
    for (i = 0; i < arrsize; i++)
        for (j = i; j < arrsize; j++)
            if (arr[i] > arr[j])
                swap(arr[i], arr[j]);
}

int recbin_search(int arr[], const int& first, const int& last, 
                  const int& key)
{
    int mid;
        
    if (first <= last) {
        mid = (first + last) / 2;
        if (key == arr[mid])
            return mid;
        else if (key < arr[mid])
            return recbin_search(arr, first, mid - 1, key);
        else
            return recbin_search(arr, mid + 1, last, key);
    }
    return -1;
}

int main()
{
    #ifdef TC
        clrscr();
    #endif
    const int MAXSIZE = 20;
    static int* arr;
    int n, ele;
    char res[MAXSIZE];
    int i;
    
    do {
        cout << "Enter the array size (1-" << MAXSIZE << "): ";
        cin >> n;
    } while (n < 1 || n > MAXSIZE);
    arr = new int[n];
    
    cout << "Now enter " << n << " elements for the array: ";
    for (i = 0; i < n; i++)
        cin >> arr[i];
    cout << "Element to be searched: ";
    cin >> ele;
    
    sort(arr, n);    
    cout << endl << "Recursive binary search in sorted, ";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "list." << endl;

    cout << "Search result - ";
    strcpy(res, recbin_search(arr, 0, n - 1, ele) > -1 ? 
           "Element found." : "Element not found!");
    cout << res;
    
    cout << endl << endl << "Program over. Press any key to exit...";
    getch();
    return 0; // Successful termination.
}