#include<stdio.h>
int insertion_sort(int a[],int n)
{
    int i,j,key;

    for(j=1;j<n;j++)
    {
        key = a[j];
        i=j-1;
        while(i>=0 && a[i]>key)
        {
            a[i+1]=a[i];
            i=i-1;
        }
        a[i+1]=key;
    }
    for(i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
}
int bin_search(int a[],int n)
{
    int i,key,end,mid;
    printf("Enter your key: ");
    scanf("%d",&key);
    i=0;
    end = n-1;
    mid = ((i+end)/2);
    while(i<=end && a[mid]!= key)
    {
        if(key<a[mid])
        {
            end = mid-1;
        }
        else i = mid+1;

         mid =(i+end)/2;
    }
    if(i>end)
    {
        return -1;
    }
    return mid;
}
int lin_search(int a[],int n)
{
    int i,key;
    printf("Enter your key: ");
    scanf("%d",&key);
    for(i=0;i<n;i++)
    {
        if(a[i] == key)
        {
            return i;
        }
    }
    return -1;
}
void menu()
{
    int n,i,o,pos2;
    printf("How many inputs: ");
    scanf("%d",&n);
    int a[n];
    printf("Enter your numbers: ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("1. Linear Search.\n");
    printf("2. Binary Search.\n");
    scanf("%d",&o);
    if(o == 1)
    {
        int pos2 = lin_search(a,n);
        if(pos2==-1)
        {
            printf("Not found\n");
        }
        else printf("position is : %d\n",pos2);
    }
    else if(o == 2)
    {
        printf("Array is not sorted!\n");
        insertion_sort(a,n);
        printf("\n");
        int pos1 = bin_search(a,n);
        printf("position is %d\n",pos1);
    }
    else printf("Invalid input!!\n");

}
int main()
{
    menu();