Binary search

[somnathsarode]

Hey i have created binary search prograram
this progaram search all locations but not first
if i give value of other than zero location it gives results
but not for zero location
please guid me
the code is as follows

// 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;

}

[ddanbe]

At first sight there seems to be nothing wrong with your search.
Is your input sorted? This is rather essential.

[Ahmed_I]

Your Binary Search Function's logic is right but You have some simple errors :-
Firstly in the function since u intending using Recursion then u have to return the value that is resulted from the backtracking to a Variable and return this Variable to the Main function.

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;
}

Secondly:-
In the main function in case '2' when the function returns the index of the first value of the array to variable i the index that will be returned is 0
and since u made a check if i>0 only it will print "Value is not found"
here is the correction

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;
}

Thirdly:-
MAKE SURE that the values stored in the array is SORTED .

I'll be happy of Any critique .

[ddanbe]

result=bsearch(a,lb,mid-1,target);

Quite right Ahmed_l, I overlooked it! But it is easier to say : return bsearch(a,lb,mid-1,target); that way you don't need the extra result variable.

[Ahmed_I]

Quite right Ahmed_l, I overlooked it! But it is easier to say : return bsearch(a,lb,mid-1,target); that way you don't need the extra result variable.

Mr ddanbe,
It is only matter of style not more and this is a small program so it doesn't matter if i added another variable, ofcourse u right and thanks for this advice.

[ddanbe]

this is a small program so it doesn't matter

I was not making any criticism here. If you want to use a variable, please do. Nobody will get hurt.
But in programming you must always be aware of optimisation, so if you can, do it.

[somnathsarode]

hey u have not solve my problem
do u undetstand my problem
its not givinig 1 st locatotion value
when search for frist location

[somnathsarode]

yes

[Ahmed_I]

Excuse me, But could you plz explain your problem more efficiently.
cuz i didn't get your point

[ddanbe]

If you are searching for the number 3(target) and if a[0) contains 3 you will get the index which is 0 you will not get the value which is 3, but that was the value you where searching in the array a. So 0 means you found the value 3 in the array, otherwise if the value 3 was not in your array you would have gotten the value -1.