// To implement binary search using array

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

int binsearch(int ary[], int left, int right, int key){
    int mid = (left + right)/2;
    
    if( left > right )
        return -1; // searched item not found

    if( ary[mid] == key )
        return mid;
    else if( key < ary[mid] )
        return binsearch( ary, left, mid-1, key);
    else
        return binsearch( ary, mid+1, right, key);
}

int main(){
    int a[20];
    int n, x, r, i;
    
    printf("\n Enter total number of elements in array (max. %d): ", MAX);
    scanf("%d", &n);
    
    if( n < 0)
        printf("UNDERFLOW \n");
    else if( n > MAX)
        printf("OVERFLOW \n");
    else{
        // input elements one by one
        printf("\n Enter item(s) one by one in increasing order\n");
        for( i=0; i<n; i++){
            printf(" Enter item no %d : ",i);
            scanf("%d", &a[i]);
        }
    
        printf("\n Enter key to search : ");
        scanf("%d", &x);
    
        r = binsearch( a, 0, n-1, x);
        if( r >= 0 )
            printf("\n Searched result found at %dth index.\n", r );
        else
            printf("\n Searched result not found. \n");
    }
        
    system("pause");
    return 0;
}