Thread: Binary search using recursion...don't know what I am doing wrong

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    27

    Binary search using recursion...don't know what I am doing wrong

    I need to write a recursive function to perform a binary search on an array of 30.

    This is what I got so far, I think I have done everything correctly, but I can't see the error in the code.

    Code:
    int find_array(int a[], int left, int right, int elem);
    
    int main ()
    {
    	int a[] = {
    	1,	4,	6,	8,	9,	10,	13,	16,	17,	19,
    	20,	21,	30,	32,	33,	35,	37,	39,	50,	70,
    	71,	73,	79,	81,	85,	87,	95,	96,	97,	99 };
    
    
    	int size = sizeof(a) / sizeof(int);
    
    	int num, index;
    
    	while (num != 0)
    	{
    		printf("Enter a positive number: ");
    		scanf("%d", &num);
    
    		if (num == 0)
    		{
    			;
    		}
    
    		else
    		{
    
    			index = find_array(a, 0, size-1, num);
    
    			if (index == -1)
    			{
    				printf("%d is not included\n", num);
    			}
    
    			else
    			{
    				printf("%d is at index %d\n", num, index);
    			}
    		}
    	}
    	return 0;
    }
    
    int find_array(int a[], int left, int right, int elem)
    {
    	int middle;
    
    	if (left > right)
    	{
    		return -1;
    	}
    
    	else
    	{
    		middle = left + (right-left) / 2;
    
    		if (elem == a[middle])
    		{
    			return middle;
    		}
    
    		else
    		{
    			if (elem < a[middle])
    			{
    				find_array(a, 0, middle-1, elem);
    			}
    
    			else 
    			{
    			find_array(a, middle+1, right, elem);
    			}
    		}
    	}
    }
    Please help, thanks.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    find_array(a, 0, middle-1, elem);
    You shouldn't be hard coding the value '0' in your find function. It should be 'left' instead of '0'.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    27
    Thanks, the problem is that index is giving me the value "2008958736" for each positive value I enter. I have no iedea where that number is coming from, what I do know is that something is wrong, but I don't believe I have done something wrong...at least I can't see it. I'm new in C btw...

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You need to be returning a value at every step in the program. Walk through your program:
    Code:
    int find_array( ... )
    {
    	if( left > right )
    		return -1;
    	else
    	{
    		middle = left + (right-left) / 2;
    
    		if (elem == a[middle])
    		{
    			return middle;
    		}
    		else
    		{
    			if (elem < a[middle])
    			{
    				find_array(a, 0, middle-1, elem);
    			}
    			else 
    			{
    			find_array(a, middle+1, right, elem);
    			}
    		}
    	}
    	/* Uh oh! We get here with nothing returned! */
    }
    Walk through this with the following array:
    Code:
    array[] = { 1, 2, 3 }
    
    index = find_array( ... 2 );
    We're trying to find 2 here.
    Running through your program:
    Code:
        left is not greater than right, so don't return -1
        if elm is what we're looking for, return it, it isn't ,so we continue
    
        we have a recursive call now, the return value of which is discarded
    
            we're in the first recursive call
            the -1 check passes, so we keep going
            this slot is what we're looking for, so we return it
    
        we now have exited the recursive call
        the value we just returned was discarded
        we now drop out of all } } } } lines
        we reach the end of the function, nothing is returned[
    Actually something is returned, but it's some undefined piece of memory, which is why you get what you get.

    You should modify your recursive calls to something like:

    return find_array(a, middle+1, right, elem);

    Just remember this key thought: Whenever a function exits, if it is a non-void function, it must return something.

    Your compiler should be warning you about reaching the end of a function and not returning something. Pay attention to your compiler.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Oct 2003
    Posts
    27
    Thanks a lot!

    I'll remember your tips and advice!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary search on strings
    By ckathy in forum C++ Programming
    Replies: 1
    Last Post: 10-02-2007, 05:25 PM
  2. How to search within a binary file
    By khpuce in forum C Programming
    Replies: 17
    Last Post: 04-12-2005, 05:23 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. Ornery binary search algorithm
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 11-17-2001, 03:32 PM