Thread: Will this binary search implementation of mine work??

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    32

    Will this binary search implementation of mine work??

    Right now, its compiling and seg faulting..

    Can anyone tell me

    a) Why it is seg faulting

    b) Is this the right implementation

    c) What is a more elegant way to do this

    Thanks so much!

    Avanish

    Code:
    int main(){
    
    
    int array[101];
    
    
    int i;
    
    
    for ( i=0 ; i<101; i++ )
            array[i] = i;
    
    
    printf("Enter a number to search in the list 1-99\n");
    int num;
    scanf("%d",&num);
    
    
    int length = 100;
    int start_search = 0;
    int end_search = length;
    search(num, array, start_search, end_search);
    
    
    }
    
    
    void search(int num, int* array, int start_search, int end_search){
    
    
    if( array[end_search] == num ){
            printf("array[%d] = %d",end_search,array[end_search]);
            return;}
    else if( array[end_search/2] < num )
            search(num, array, start_search, end_search/2);
    else search(num, array, end_search/2, end_search);
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Put the loop for the search, within the search function, and have it return the result of the search to your (parent) function.

    Code:
    Get the parameters. in a loop, perhaps.
        Call binary search and read the return from binary search function.
    and loop.
    
    int binary_search(int floor, int celing, int array[MAXSIZE])
       while(floor is less than or equal to ceiling) {
          binary search code, goes here
       }
       return result
    }






    Guess a number from 1 to 10:

    guess: 5
    too high
    new ceiling is set at 4
    guess: 2
    too low
    new floor is set at 3
    guess: 3
    too low
    new floor is set to 4
    guess: 4
    correct!

    Read up on this in the Wikipedia and /or Google. You want a while (natural feel to it), or a for loop, in the binary search function.
    Last edited by Adak; 05-05-2012 at 08:30 PM.

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Adak View Post
    You want a while (natural feel to it), or a for loop, in the binary search function.
    He's doing it the recursive way, applying the same binary search called with different arguments for the remaining half spaces.
    What would a loop do there ?

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    32
    Can anyone tell me what exactly is going wrong with my code, for pedagogical purposes?

    This isn't homework by the way, it is pure recreation.

    I do think I have the concept of binary search fairly understood, Adak, but I could be mistaken.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    My bad. I've never even seen a binary search done recursively.

    The parameters should be either floor=guess+1, or ceiling=guess-1.

    Why use division?

    No, I see that now. To be honest, a spider fell down just a bit ago, and bit me right below my left eye, and I'm a bit distracted atm.

  6. #6
    Registered User
    Join Date
    Mar 2012
    Posts
    32
    Sorry, I'm still confused. Does anyone see why this seg faults. Obviously something is wrong but it seems to me like it should work..

  7. #7
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Avanish Giri View Post
    Sorry, I'm still confused. Does anyone see why this seg faults. Obviously something is wrong but it seems to me like it should work..
    Learn how to use a debugger.
    (It is almost surely a problem with bad pointers/offsets at some point.)
    You also did not define a "not found" condition and went around recursing past that, that could be the cause.
    Last edited by manasij7479; 05-05-2012 at 08:48 PM.

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I've never even seen a binary search done recursively.
    O_o

    I'm sure you've just forgotten in favor of the iterative approach because that would be insanely weird.

    Soma

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    a) Hard to say for sure, but I'm guessing it has to do with how you make your recursive call, i.e. something to do with end_search/2 not always being what you want. Learn to use a debugger (see below).

    b) Apart from the fact that it seg faults, no, it does not work. A general rule, asking us if something is correct implies laziness on your part, namely that you were too lazy to test it yourself. Try stepping through your code by hand, on paper. Use a small array, with, say, 10 or 16 elements. Also realize that your array must be sorted for a binary search to work. What happens if you can't find the number?

    c) You can't get much more elegant that you have right now. That's about all there is to a binary search (except for the "not found" case I mentioned). The only thing you don't need is that return; on line 33. The else if/else ensures that you will only call the printf, then return.

    As for why it seg faults, you are blowing out your call stack. Generally, with recursive functions, this is because you don't cover all possible base cases and/or your recursive calls don't narrow down the data set you are working with. In your case, it's the latter. The blue is what I typed, the green is what your program output. The red is the problem: you keep making the same recursive call.
    Code:
    $ gcc -g -Wall -std=c99 -o foo foo.c
    $ gdb foo
    GNU gdb (GDB) Fedora (7.3-43.fc15)
    Copyright (C) 2011 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "i686-redhat-linux-gnu".
    For bug reporting instructions, please see:
    <http://www.gnu.org/software/gdb/bugs/>...
    Reading symbols from /home/cagarvin/sandbox/cprogramming/foo...done.
    (gdb) r
    Starting program: /home/cagarvin/sandbox/cprogramming/foo
    [Thread debugging using libthread_db enabled]
    Enter a number to search in the list 1-99
    42
    
    
    Program received signal SIGSEGV, Segmentation fault.
    0x08048665 in search (num=42, array=0xbffff3ec, start_search=50, end_search=100) at foo.c:33
    33          else search(num, array, end_search/2, end_search);
    Missing separate debuginfos, use: debuginfo-install cyrus-sasl-lib-2.1.23-18.fc15.i686 glibc-2.14.1-6.i686 keyutils-libs-1.2-7.fc15.i686 krb5-libs-1.9.2-6.fc15.i686 libcom_err-1.41.14-2.fc15.i686 libselinux-2.0.99-4.fc15.i686 nspr-4.8.9-2.fc15.i686 nss-3.13.1-11.fc15.i686 nss-softokn-freebl-3.13.1-15.fc15.i686 nss-util-3.13.1-3.fc15.i686 openldap-2.4.24-3.fc15.i686 openssl-1.0.0g-1.fc15.i686 postgresql-libs-9.0.7-1.fc15.i686 zlib-1.2.5-3.fc15.i686
    (gdb) bt
    #0  0x08048665 in search (num=42, array=0xbffff3ec, start_search=50, end_search=100) at foo.c:33
    #1  0x0804867f in search (num=42, array=0xbffff3ec, start_search=50, end_search=100) at foo.c:33
    #2  0x0804867f in search (num=42, array=0xbffff3ec, start_search=50, end_search=100) at foo.c:33
    ...
    #20122 0x0804867f in search (num=42, array=0xbffff3ec, start_search=50, end_search=100) at foo.c:33
    #20123 0x0804867f in search (num=42, array=0xbffff3ec, start_search=50, end_search=100) at foo.c:33

  10. #10
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by phantomotap View Post
    I'm sure you've just forgotten in favor of the iterative approach because that would be insanely weird.
    Will this binary search implementation of mine work??-sohardcore-jpg
    Couldn't resist!

  11. #11
    Registered User
    Join Date
    Mar 2012
    Posts
    32
    Andurii, thank you, that was exactly what I was looking for. To be honest, I tried running it in gdb, I did! I got to the point where I said backtrace, but it didn't show me the variables as it did for you... It just showed me the hex addresses and all of the calls.

    Although I have already overstepped my boundaries and been a lazy man, I would like to ask how you got gdb to show you the code you posted. But, expecting you will not answer, thanks anyways for posting that.

    Avanish

  12. #12
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Avanish Giri View Post
    Although I have already overstepped my boundaries and been a lazy man, I would like to ask how you got gdb to show you the code you posted. But, expecting you will not answer, thanks anyways for posting that.
    Compile with debugging symbols.

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I would like to ask how you got gdb to show you the code you posted.
    Why not read the "GDB" manual while we wait?

    Couldn't resist!
    Heh.

    It applies to your post.

    Soma

  14. #14
    Registered User
    Join Date
    Mar 2012
    Posts
    32
    Actually I just realized that I had my comparison operator backwards. It should be if ( array [ end_search / 2 ] > num ) ....

    But it still seg faults.. I do not get it. But I feel as though I have exhausted this resource for some reason so thank you all.

  15. #15
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I do not get it.
    O_o

    You don't get it even after seeing the values?

    Wow.

    Okay, do this by hand assuming a value greater than 50 was entered:

    What is the value of max range?
    What is the value of max range divided by two?
    What is the value of max range on the second recursion? Oops.

    As was implied, to my mind, by anduril462, simply dividing the end or the range by two is not sufficient to get the middle of the range.

    Please, stop banging your head against the wall trying to understand something you don't by coding it; that will never work. You have to understand something before you can code it.

    Unlike Adak, the world has seen a lot of recursive binary searches. Please go read about them before writing more code.

    Soma

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with a binary search tree implementation
    By mrwall-e in forum C Programming
    Replies: 0
    Last Post: 04-29-2012, 12:34 PM
  2. Need soem suggestions on my Binary Search Tree Implementation
    By indigo0086 in forum C++ Programming
    Replies: 14
    Last Post: 10-10-2007, 10:20 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. Searching a binary search tree - doesn't work
    By Ariod in forum C Programming
    Replies: 1
    Last Post: 08-11-2005, 03:53 PM
  5. Canīt get glut work with mine BORLAND compiler
    By ripper079 in forum Game Programming
    Replies: 5
    Last Post: 12-19-2001, 09:15 AM