Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Simple program to implement binary search |
| Date | 2015-11-12 16:53 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <n22g19$dml$1@dont-email.me> (permalink) |
| References | <af16475b-9f9c-46f8-98c5-9353f82423da@googlegroups.com> |
On 12/11/15 16:12, Alla _ wrote:
>
> I have tested the program on paper, for these numbers, and I don't
> see why it doesn't work.
I'm struggling to see how it could possibly work. Fortunately, the fix
is quite a simple one.
> // Program to perform binary search
>
<snip>
>
> printf("Name your number: \n");
> scanf("%i", &number);
If you persistently ignore advice, you run the risk that people will
stop bothering to help you.
scanf can *fail*, and you should check for this.
Also, %i's behaviour can be unexpected to the unwary. I recommend that
you use %d, as has already been explained to you before.
> // Function to perform binary search
Okay, let's look at this.
> bool binary_search(int search_value, int numbers[], int min_val, int max_val)
> {
>
> if (max_val < min_val)
> return false;
>
> int mid_index = (max_val + min_val) / 2;
>
> if (search_value > numbers[mid_index])
> binary_search(search_value, numbers, mid_index+1, max_val);
How are you going to tell whether this recursive call to binary_search()
found anything? You don't check the return value!
> else if (search_value < numbers[mid_index])
> binary_search(search_value, numbers, min_val, mid_index-1);
Likewise.
> else
> return true;
>
> return false;
> /** I had to add the last return false; part because
> without it the compiler generated a warning:
> warning: control reaches end of non-void function **/
There's a reason for that - the return value is *important*! But you
didn't bother to check it when you yourself called binary_search() in
the above two examples.
Here is the function again, with some very slight changes, and the
significant difference that it now works for your test data (1-5). I
also checked 0 and 6 to ensure that they were *not* found:
// Function to perform binary search
bool binary_search(int search_value,
int numbers[],
int min_val,
int max_val)
{
bool found = false;
if (max_val < min_val)
return false;
/* The above "early return" is something I don't like to do, but I was
trying for a light touch, and this line did not, strictly speaking, need
to be changed, so I left it alone. */
int mid_index = (max_val + min_val) / 2;
if (search_value > numbers[mid_index])
found = binary_search(search_value,
numbers,
mid_index+1,
max_val);
/* Note that we *record* the result of the search, in the 'found' object
in the "guess is too small" part... */
else if (search_value < numbers[mid_index])
found = binary_search(search_value, numbers, min_val,
mid_index-1);
/* And again in the "guess is too big" part... */
else
found = true;
/* ...and again in the "got it!" part. */
return found; /* ...and here, we return the result of the search */
}
Now it works.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 08:12 -0800
Re: Simple program to implement binary search Frank Tetzel <s1445051@mail.zih.tu-dresden.de> - 2015-11-12 17:45 +0100
Re: Simple program to implement binary search John Gordon <gordon@panix.com> - 2015-11-12 16:49 +0000
Re: Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 10:11 -0800
Re: Simple program to implement binary search Richard Heathfield <rjh@cpax.org.uk> - 2015-11-12 18:13 +0000
Re: Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 10:24 -0800
Re: Simple program to implement binary search Richard Heathfield <rjh@cpax.org.uk> - 2015-11-12 18:41 +0000
Re: Simple program to implement binary search Chad <cdalten@gmail.com> - 2015-11-12 11:56 -0800
Re: Simple program to implement binary search Richard Heathfield <rjh@cpax.org.uk> - 2015-11-12 16:53 +0000
Re: Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 10:23 -0800
Re: Simple program to implement binary search Richard Heathfield <rjh@cpax.org.uk> - 2015-11-12 18:35 +0000
Re: Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 10:50 -0800
Re: Simple program to implement binary search supercat@casperkitty.com - 2015-11-12 11:17 -0800
Re: Simple program to implement binary search Barry Schwarz <schwarzb@dqel.com> - 2015-11-12 11:20 -0800
Re: Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 23:20 -0800
Re: Simple program to implement binary search Richard Heathfield <rjh@cpax.org.uk> - 2015-11-13 07:23 +0000
Re: Simple program to implement binary search Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-12 10:20 -0800
Re: Simple program to implement binary search Alla _ <modelling.data@gmail.com> - 2015-11-12 10:57 -0800
Re: Simple program to implement binary search Richard Heathfield <rjh@cpax.org.uk> - 2015-11-12 19:01 +0000
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-14 11:19 -0800
Re: Simple program to implement binary search Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-14 12:52 -0800
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-15 12:48 -0800
Re: Simple program to implement binary search raltbos@xs4all.nl (Richard Bos) - 2015-11-17 22:54 +0000
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-20 13:47 -0800
Re: Simple program to implement binary search "Charles Richmond" <numerist@aquaporin4.com> - 2015-11-21 18:26 -0600
Re: Simple program to implement binary search Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-22 08:19 -0500
Re: Simple program to implement binary search mark.bluemel@gmail.com - 2015-11-26 01:08 -0800
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-22 13:42 -0800
Re: Simple program to implement binary search "Charles Richmond" <numerist@aquaporin4.com> - 2015-11-23 15:47 -0600
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-24 08:44 -0800
Re: Simple program to implement binary search Les Cargill <lcargill99@comcast.com> - 2015-11-16 22:52 -0600
Re: Simple program to implement binary search Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-17 01:02 -0800
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-20 13:27 -0800
Re: Simple program to implement binary search Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-13 21:41 -0800
csiph-web