/* 1.(a) W.A.P. to search for a given element in a list of size 'n' using the recursive binary search. Compute the time taken for executing this program. */

#include<stdio.h>
#include<conio.h>
#include<time.h>
clock_t start,finish;
int BinSearch(int a[],int low,int high,int key)
{
    int mid;
    if (low > high) return -1;
        mid = (low + high) / 2;
    if (a[mid] == key)
        return mid;
    else if (a[mid] > key)
        return (BinSearch(a,0,mid-1,key));
    else
        return (BinSearch(a,mid+1,high,key));
}
void main()
{
    int i,n,*a,key,pos;
    clrscr();
    printf("How many elements you wish to enter : ");
    scanf("%d",&n);
    a = (int *)malloc(n * sizeof(int));
    printf("\nEnter %d elements : ",n);
    for (i = 0; i < n; i++)
        scanf("%d",&a[i]);
    printf("\nEnter the key element to be searched : ");
    scanf("%d",&key);
    start = clock();
    pos = BinSearch(a,0,n-1,key);
    if (pos == -1)
        printf("\n\n*** Search Failure ***");
    else
    {
        printf("\n\n*** Search Successful ***\n");
        printf("Key element found at position no. %d",pos+1);
    }
    finish=clock();
    printf("\n\nTime taken to search is %.2f",(finish - start) / CLK_TCK);
    getch();
}
/* OUTPUT
How many elements you wish to enter : 6
Enter 6 elements : 3 5 6 9 10 17
Enter the key element to be searched : 9
*** Search Successful ***
Key element found at position no. 4
Time taken to search is 0

How many elements you wish to enter : 4
Enter 4 elements : 43 56 76 89
Enter the key element to be searched : 0
*** Search Failure ***
Time taken to search is 0
*/