DaniWeb Forum Index > Software Development > C

C RSS

Recursive binary search

•

Join Date: Sep 2004

Posts: 1

Reputation: Sushi is an unknown quantity at this point

Solved Threads: 0

Sushi

Offline

Newbie Poster

Recursive binary search

Sep 22nd, 2004

I'm trying to write a function that gets an array, it's size and the number I'm looking for. The function should be recursive.
That's what I've written, it doesn't work. I don' understand why. Suggestions are welcome.

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
 #include <stdio.h> 
int binary (int *a, int n, int num)
{
	int temp = n/2;
	int c = -1;
	 if (n==1)
	 {
              	 if (*a == num)
		  return (*a-1);
                         else return c;
	 }    
 
	if (a[temp] < num)
		return binary ((a+temp+1), (temp-1), num);
	else return binary (a, (temp+1), num);
 
 return (a + temp) ;
}
 
int main (void)
{
 
int a[5] = {1, 2, 3, 4, 5};
int n = 5, num =0;
printf ("%d", binary (a, n, num));
return 0; 
}
 #include <stdio.h> 
int binary (int *a, int n, int num)
{
	int temp = n/2;
	int c = -1;
	 if (n==1)
	 {
              	 if (*a == num)
		  return (*a-1);
                         else return c;
	 }    
     
	if (a[temp] < num)
		return binary ((a+temp+1), (temp-1), num);
	else return binary (a, (temp+1), num);

 return (a + temp) ;
}

int main (void)
{
 
int a[5] = {1, 2, 3, 4, 5};
int n = 5, num =0;
printf ("%d", binary (a, n, num));
return 0; 
}

Plus, I'm looking for programs that use backtracking, or some explanation on te subject of backtracking. Anyone know any helpful sites?
Thanks, S.u.s.h.i.

Last edited by Narue; Apr 23rd, 2009 at 4:53 pm. Reason: added code tags

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 10

Chainsaw

Offline

Unprevaricator

Re: Recursive binary search

Sep 22nd, 2004

Why does it need to be recursive? Just because that's the assignment? Non-recursive binary searches are one of life's simple beauties.

In this case, stepping through a debugger would be helpful, but you don't return the value when its found because you test for < num but not == num. that is, you say if a[temp] < num binary(upper half) else binary(lower half); you forgot if a[temp] == num return temp.

More than that, though is the question "what does the routine return" I would think you want to return the INDEX of where it is found; it looks like you are returning the contents sometimes.

•

Join Date: Apr 2009

Posts: 1

Reputation: tyameh is an unknown quantity at this point

Solved Threads: 0

tyameh

Offline

Newbie Poster

A C program for Recursive binary search

-2

Apr 23rd, 2009

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
#include<stdio.h>
#include<conio.h>
void main()
{
	int a[10],i,item;
	void binary(int x[10],int beg,int end,int y);
	clrscr();
	for(i=0;i<10;i++)
	{
		printf("enter no.:");
		scanf("%d",&a[i]);
	}
	printf("enter no. to be found:");
	scanf("%d",&item);
	binary(a,0,9,item);
	getch();
}
void binary(int x[10],int beg,int end,int y)
{
	int mid,z;
	if(beg<=end)
	{
		mid=(beg+end)/2;
		if(x[mid]==y)
		{
			printf("number found");
		}
		if(y<x[mid])
		{
			end=mid-1;
			binary(x,beg,end,y);
		}
		else
		{
			beg=mid+1;
			binary(x,beg,end,y);
		}
	}
}
#include<stdio.h>
#include<conio.h>
void main()
{
	int a[10],i,item;
	void binary(int x[10],int beg,int end,int y);
	clrscr();
	for(i=0;i<10;i++)
	{
		printf("enter no.:");
		scanf("%d",&a[i]);
	}
	printf("enter no. to be found:");
	scanf("%d",&item);
	binary(a,0,9,item);
	getch();
}
void binary(int x[10],int beg,int end,int y)
{
	int mid,z;
	if(beg<=end)
	{
		mid=(beg+end)/2;
		if(x[mid]==y)
		{
			printf("number found");
		}
		if(y<x[mid])
		{
			end=mid-1;
			binary(x,beg,end,y);
		}
		else
		{
			beg=mid+1;
			binary(x,beg,end,y);
		}
	}
}

Last edited by Narue; Apr 23rd, 2009 at 4:53 pm. Reason: added code tags

•

Join Date: Sep 2004

Posts: 7,625

Reputation: Narue has a reputation beyond repute

Solved Threads: 714

Narue

Offline

Code Goddess

Re: Recursive binary search

Apr 23rd, 2009

When somebody bumps a thread that hasn't been touched in years to post code, it's pretty much always crap riddled with poor practices. Coincidence? Probably not.