Recursive binary search program help.

This is a discussion on Recursive binary search program help. within the C Programming forums, part of the General Programming Boards category; Im attempting to write a binary search function which calls itself recursively. I cant get it to call itself recursively ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    4

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

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    4

    Talking

    Quote Originally Posted by Todd Burch View Post
    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!

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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.
    Last edited by iMalc; 04-04-2008 at 01:19 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Client-server system with input from separate program
    By robot-ic in forum Networking/Device Communication
    Replies: 3
    Last Post: 01-16-2009, 02:30 PM
  2. help with c program: binary to ascii program
    By bigmac(rexdale) in forum C Programming
    Replies: 26
    Last Post: 02-03-2008, 01:26 PM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. binary search program
    By galmca in forum C Programming
    Replies: 5
    Last Post: 01-24-2005, 11:00 PM
  5. Binary Search in C help
    By kce9751 in forum C Programming
    Replies: 2
    Last Post: 06-17-2003, 08:17 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21