Recursive binary search program help.

Im attempting to write a binary search function which calls itself recursively. I cant get it to call itself recursively w/ out freezing. The code is below, it freezes right after "calling function recursively"

I tried setting found =1 right before it calls itself, but that doesn't work meaning the program doesnt get stuck in an infinite loop, it just freezes when it calls itself.

I think it might have to do w/ allocating and freeing the memory, but am really not sure.

Thanks for the help!

Code:

#include <stdio.h>

	
int
BinarySearch(int *asize, int numbers[*asize], int *snum, int *searcher, int *iter, int *top, int *bottom, int *middle, int *found)
{

	*middle = (int)(((*top + *bottom)/2.0)+.5);	
	printf("top = %d middle = %d bottom = %d\nsearcher = %d snum = %d &numbers[*middle] = %d found = %d", *top, *middle, *bottom, *searcher, *snum, numbers[*middle], *found);

	if(*bottom < *top && *found == 0) {
		if(searcher == numbers[*middle]) {
			*found = 1;
			*iter++;
			printf("found %d", &numbers[*middle]);
		}
		else if(numbers[*middle] > *searcher) {
             *top = *middle - 1;
             printf("top = %d middle = %d bottom = %d\nsearcher = %d snum = %d &numbers[*middle] = %d", *top, *middle, *bottom, *searcher, *snum, numbers[*middle]);
            printf("calling function recursively");
            return (BinarySearch(*asize, numbers, *snum, *searcher, *iter, *top, *bottom, *middle, *found));
        }
        else {
             *bottom = *middle + 1;  
             printf("top = %d middle = %d bottom = %d\nsearcher = %d snum = %d &numbers[*middle] = %d", *top, *middle, *bottom, *searcher, *snum, numbers[*middle]);
             return (BinarySearch(*asize, numbers, *snum, *searcher, *iter, *top, *bottom, *middle, *found));
        }     
      
    }
    else{}
    
    if(*found == 1) {
         return(0);
         }
    else {
         printf("top = %d middle = %d bottom = %d\nsearcher = %d snum = %d &numbers[*middle] = %d", *top, *middle, *bottom, *searcher, *snum, numbers[*middle]);
        

    }
}

When you call BinarySearch recursively here:

Code:

return (BinarySearch(*asize, numbers, *snum, *searcher, *iter, *top, *bottom, *middle, *found));

You are using the indirection operator on most all of the variables. As an example, asize is a pointer, and you are telling the compiler to pass what asize points to, which is an int, as opposed to just passing the pointer.

Lose the indirection operator and try it.

Todd

Originally Posted by Todd Burch

When you call BinarySearch recursively here:

Code:

return (BinarySearch(*asize, numbers, *snum, *searcher, *iter, *top, *bottom, *middle, *found));

You are using the indirection operator on most all of the variables. As an example, asize is a pointer, and you are telling the compiler to pass what asize points to, which is an int, as opposed to just passing the pointer.

Lose the indirection operator and try it.

Todd

THANKS!

Code:

int
BinarySearch(int *asize, int numbers[*asize], int *snum, int *searcher, int *iter, int *top, int *bottom, int *middle, int *found)

What are all those 9 parameters for? A binary search usually takes just 4 parameters, though it can be optimised down to just 3.

You should start over with just 4 parameters. The parameters are:
1. The array to search (of course). This should be just a pointer to the array. The declaration of this pointer should be the only place a * appears in the entire function, unless you use [] in the declaration instead in which case there will be no *'s in the whole function.
2 & 3. The high and low values to search between. Not pointers - you only want to tell it what subrange to search, nothing more.
4. The value to search for (of course). Not a pointer.

Using floating point math is pointless here. Converting between floating point and integers is quite slow. Rounding gives you nothing either. One way or another one of the partitions is going to be smaller than the other; it doesn't make the slightest bit of difference which one is. Just let the division truncate the result.

You should remove those printf's, they will only confuse you. If you really want to see what is happening, step through it with your debugger.

Turn up the warning level of your compiler, or pay attention to the warnings it is giving you. There are control paths that don't return a value.
What is it supposed to return anyway? The only thing it can return currently is zero.