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

1. ## 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. 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.

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. 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. 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. 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. Originally Posted by Avanish Giri
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.

8. 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. 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.
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/>...
(gdb) r
Starting program: /home/cagarvin/sandbox/cprogramming/foo
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. Originally Posted by phantomotap
I'm sure you've just forgotten in favor of the iterative approach because that would be insanely weird.

Couldn't resist!

11. 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. Originally Posted by Avanish Giri
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. 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.

Soma

14. 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. 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.