Recursive binary search

[Sushi]

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.

#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.

[Chainsaw]

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.

[tyameh]

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

[Narue]

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. :icon_rolleyes:

[joshisumitnet]

Great Binary Search Recursive Function.
Cheers. :)

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

[Mubashar.basra]

please tell how can i run this programe in c++ data structure

#include<iostream>
#include<conio.h>
using namespace std;
int binarysearch(int a[],int n,int low,int high)
    { int mid;
      if (low > high)
       return -1;
      mid = (low + high)/2;
      if(n == a[mid])
     { cout<<"the element found";
          return 0;
        }
      if(n < a[mid])
        { high = mid - 1;
          binarysearch(a,n,low,high);
        }
      else if(n > a[mid])
        { low = mid + 1;
          binarysearch(a,n,low,high);
        }
     }

main()
    { int a[50];
      int n,no,x,result;
      cout<<"Enter the number of terms : "<<endl;
      //printf("Enter the elements :\n");
      //for(x=0;x<50;x++)

      //cout<<"Enter the number to be searched : ";

      result = binarysearch(a,n,0,no-1);
      if(result == -1)
   cout<<"Element not found";
      getch();
      return 0;
    }

[WaltP]

As Narue said 2.5 years ago... :icon_rolleyes: