/* 8. Input n followed by n non-repeated numbers. Sort the numbers using Bubble sort, Conduct Binary Search for the given number and report success or failure. In case of success report number of probes.  */

#include<stdio.h>
void main()
{
    int i,j,n,a[25],temp,flag,exchg=0,begin=1,key,end,mid=0,probe=0;
    clrscr();
    printf("Enter a number : ");
    scanf("%d",&n);
    if (n>0)
    {
        printf("\nEnter %d elements in the list.\n",n);
        for (i=0; i<n; i++)
        {
            printf("Number%d ==>> ",i+1);
            scanf("%d",&a[i]);
        }
        for (i=0; i<n-1; i++)
        {
            flag=1;
            for (j=0; j<n-1-i; j++)
            {
                if (a[j]>a[j+1])
                {
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=0;
                    exchg++;
                }
            }
            if (flag) break;
        }
        printf("\n\nSorted list is as follows :\n");
        for (i=0; i<n; i++)
            printf("\n%-d",a[i]);
            
        // BINARY SEARCH
        printf("\n\nEnter the key element to be searched in the above sorted list : ");
        scanf("%d",&key);
        end=n-1;
        while ((key!=a[mid]) && (begin<=end))
        {
            probe++;
            mid=(begin+end)/2;
            if (key<a[mid]) end=mid-1;
            else if (key>a[mid]) begin=mid+1;
        }
        if (a[mid]==key)
        {
            printf("\n\nSearch successfull and element found at %d",mid+1);
            printf("\nNumber of probes=%d",probe);
        }
        else
            printf("\n\nSearch Failure");
    }
    else printf("\n!!! Invalid Input Entry. Please Try Again !!!");
    getch();
}