// Program for Binary search
#include<stdio.h>
#include<conio.h>
int a[50];
void main()
{
	int ch1=0,n=0,i;
	clrscr();
	while(ch1!=4)
	{
		printf("\n 1 : Read data ");
		printf("\n 2 : Search data ");
		printf("\n 3 : Show data ");
		printf("\n 4 : Exit ..... ");
		printf("\n Enter your choice: ");
		scanf("%d",&ch1);
		switch(ch1)
		{
			case 1:
				printf("\n Enter no of values to read : ");
				scanf("%d",&n);
				for(i=0;i<n;i++)
				scanf("%d",&a[i]);
				break;
			case 2:
				printf("\n Enter valu to be search : ");
				scanf("%d",&i);
				i=bsearch(a,0,n-1,i);
				if(i>0)
				printf("\n Value is found at index %d ",i);
				else
				printf("\n Value is not found ");
				  break;
			case 3:
				for(i=0;i<n;i++)
				printf("\n %5d",a[i]);
				break;
 
		}
	}
}
 
int bsearch(int a[],int lb,int ub,int target)
{
	int mid;
	if(lb<=ub)
	{
		mid=(lb+ub)/2;
		if(a[mid]==target)
		return mid;
		else if(a[mid]>target)
		bsearch(a,lb,mid-1,target);
		else
		bsearch(a,mid+1,ub,target);
 
	}
	else
	 return -1;
 
}

int bsearch(int a[],int lb,int ub,int target)
{
    int result; //Here is the variable that accepts the result of the backtracking
	int mid;
	if(lb<=ub)
	{
		mid=(lb+ub)/2;
		if(a[mid]==target)
		return mid;
		else if(a[mid]>target)
		result=bsearch(a,lb,mid-1,target);
		else
		result=bsearch(a,mid+1,ub,target);
 
	}
	else
	 return -1;
 
     return result;
}

case 2:
{
	printf("\n Enter valu to be search : ");
	scanf("%d",&i);
	i=bsearch(a,0,n-1,i);
	if(i>=0) //Here is the correction just add the "=" sign
	printf("\n Value is found at index %d ",i);
	else
	printf("\n Value is not found ");
	break;
}