Thread: Recursive Binary Search

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    9

    Recursive Binary Search

    Hey, guys. I'm having trouble with creating a code for a recursive binary search. Whenever I run the code, it says "Segmentation fault (core dumped)". What should I change in my code? Here it is:

    Code:
    while(lower<=upper){
        input2(&search);
        if(search==-1)
            printf("break;");
        printf("Found %d at index %d", search, binary(array, n, search, lower, upper));
        }
    
    int binary(int array, int n, int search, int lower, int upper){
    
    
    int middle;
    lower=0;
    upper=n-1;
    
    
    
    
        middle=(lower+upper)/2;
    
    
          if (array[middle] > search) // key is in lower subset
            return binary(array, n, search, lower, middle-1);
          else if (array[middle] < search) // key is in upper subset
            return binary(array, n, search, middle+1, upper);
          else // key has been found
            return middle; 
    }
    Last edited by Tim Arevalo; 07-29-2012 at 11:37 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Tidying up the formatting:
    Code:
    int binary(int array, int n, int search, int lower, int upper){
        int middle;
        lower=0;
        upper=n-1;
        middle=(lower+upper)/2;
    
        if (array[middle] > search) // key is in lower subset
            return binary(array, n, search, lower, middle-1);
        else if (array[middle] < search) // key is in upper subset
            return binary(array, n, search, middle+1, upper);
        else // key has been found
            return middle; 
    }
    If you ignore the value of upper that was passed in and set upper to n-1 every time (where n never changes), why bother passing in upper at all?
    Hint: You don't need n.

    Then consider what happens when you search for a value that is not in the array, or more specifically, a value that is either lower than all values in the array, or greater than all values in the array.
    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"

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    24
    Correct me if I am wrong but these are the things you might want to consider.

    1) Try passing the Pointer to the Array instead of the Array itself. Its expensive if you pass the whole array all the time.

    2)Like iMalc Said, You didnt consider the case where the item to be searched is not in the list. In the current condition of your code. If the Input Array is (1,2,3,4,5) and you want to search 7 in it. You will be facing an Infinite loop. You just need to check if Upper not equal Lower in the if conditions, containing the recursive calls.

    Other than that its awsome. Good Luck.
    Last edited by sunny`; 07-30-2012 at 02:33 AM.

  4. #4
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by sunny` View Post
    1) Try passing the Pointer to the Array instead of the Array itself. Its expensive if you pass the whole array all the time.
    He is already passing a pointer to the array but the function doesn't accept one:
    Code:
    int binary(int array, int n, int search, int lower, int upper)
    What type is array? Can you index it?

    A better compiler would have told Tim.

    Bye, Andreas

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    ^^^ Should be getting an error, or at least a warning, out of the int array parameter.

    Sunny, in C, you always are passing just a pointer to the array (in the form of the array name itself). Never the whole array.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Totally missed that array was not a pointer. Given he got a core dump, it obviously compiled at some point. But without a pointer there it certainly wont compile. Darn contradictory information!
    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. Recursive binary search program help.
    By mooney in forum C Programming
    Replies: 3
    Last Post: 04-04-2008, 01:12 AM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  4. recursive search
    By bhorrobi in forum Windows Programming
    Replies: 2
    Last Post: 10-03-2003, 03:41 AM
  5. recursive binary search
    By condorx in forum C Programming
    Replies: 3
    Last Post: 12-03-2002, 12:31 PM