Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #75833 > unrolled thread

Simple program to implement binary search

Back to article view | Back to comp.lang.c

Contents

  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

Page 1 of 2  [1] 2  Next page →

#75833 — Simple program to implement binary search

Hello!

Please, take a look at the simple program that should perform
a binary search - find a number in the sorted array based on
binary search algorithm.

Caveat: there are two functions in this program; one is the binary
search function, and another search function that should take in
binary search function. I understand that the second one is redundant,
but according to the task I have to use. Therefore, I have to keep the
form of this "template".

The function does compile, but when I ran it for the first time with
a search value 3, it did come up with at correct result; but when
I tried to find 1, it returned an incorrect answer:

Name your number: 
3

Found your number!
______________________

Name your number: 
1

Didn't find your number.

I have tested the program on paper, for these numbers, and I don't
see why it doesn't work.

Here is my explanation of how I see the code (you will understand
it upon looking at the program below).

For search value 1:

binary_search(1, array of numbers, 0, midpoint = 2 - 1 = 1)

1 < value of array[1] which is 2

recursive call to binary_search(1, array of numbers, 0, 0)

1 = value of array[0] which is 1

should return true. 

It doesn't.  

// Program to perform binary search

#include <stdio.h>
#include <stdbool.h>

bool binary_search(int search_value, int numbers[], int min_val, int max_val);

bool search(int value, int values[], int n);

int main(void)
{
    int array[] = {1, 2, 3, 4, 5};
    int number;
    
    printf("Name your number: \n");
    scanf("%i", &number);
    
    if (search(number, array, 5))
    {
        printf("\nFound your number!\n\n");
        return 0;
    }
    else
    {
        printf("\nDidn't find your number.\n\n");
        return 1;
    }
}

// Function to perform binary search 
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);
        
        else if (search_value < numbers[mid_index])
            binary_search(search_value, numbers, min_val, mid_index-1);
            
            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 **/
}

// Function that searches for required value using binary_search function
bool search(int value, int values[], int n)
{
    int min = 0;
    int max = n-1;
    
    if (binary_search(value, values, min, max))
        return true;
    
    else
        return false;
}

Thank you!

[toc] | [next] | [standalone]

#75838

> // Program to perform binary search
> 
> #include <stdio.h>
> #include <stdbool.h>
> 
> bool binary_search(int search_value, int numbers[], int min_val, int
> max_val);
> 
> bool search(int value, int values[], int n);
> 
> int main(void)
> {
>     int array[] = {1, 2, 3, 4, 5};
>     int number;
>     
>     printf("Name your number: \n");
>     scanf("%i", &number);
>     
>     if (search(number, array, 5))
>     {
>         printf("\nFound your number!\n\n");
>         return 0;
>     }
>     else
>     {
>         printf("\nDidn't find your number.\n\n");
>         return 1;
>     }
> }
> 
> // Function to perform binary search 
> 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);
>     else if (search_value < numbers[mid_index])
>         binary_search(search_value, numbers, min_val, mid_index-1); 
>     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 **/

Think about it. The compiler has a reason to say that. Try to follow
all possible paths in this function. Which of them does not have a
return statement? And is this correct? This return false at the end is
wrong.

Keep in mind that this is a recursive function. Think about the
recursion stack and what one return statement does.

> }
> 
> // Function that searches for required value using binary_search
> function bool search(int value, int values[], int n)
> {
>     int min = 0;
>     int max = n-1;
>     
>     if (binary_search(value, values, min, max))
>         return true;
>     
>     else
>         return false;
> }

[toc] | [prev] | [next] | [standalone]

#75839

In <af16475b-9f9c-46f8-98c5-9353f82423da@googlegroups.com> Alla _ <modelling.data@gmail.com> writes:

> The function does compile, but when I ran it for the first time with
> a search value 3, it did come up with at correct result; but when
> I tried to find 1, it returned an incorrect answer:

When you call binary_search() recursively, you need to RETURN the result
instead of just calling it.  Otherwise the return result of the recursive
call is lost.

i.e., this block of code:

>    if (search_value > numbers[mid_index])
>        binary_search(search_value, numbers, mid_index+1, max_val);
>         
>    else if (search_value < numbers[mid_index])
>        binary_search(search_value, numbers, min_val, mid_index-1);
>             
>    else
>        return true;

should look like this instead:

    if (search_value > numbers[mid_index])
        return binary_search(search_value, numbers, mid_index+1, max_val);
         
    else if (search_value < numbers[mid_index])
        return binary_search(search_value, numbers, min_val, mid_index-1);
             
    else
       return true;

-- 
John Gordon                   A is for Amy, who fell down the stairs
gordon@panix.com              B is for Basil, assaulted by bears
                                -- Edward Gorey, "The Gashlycrumb Tinies"

[toc] | [prev] | [next] | [standalone]

#75852

Of course! How could I miss that? Thank you! I have forgotten
that recursion requires return. 

[toc] | [prev] | [next] | [standalone]

#75853

On 12/11/15 18:11, Alla _ wrote:
> Of course! How could I miss that? Thank you! I have forgotten
> that recursion requires return.

Whatever gave you that idea?

*This* recursion requires a return value to be returned and tested, 
because it was designed that way. That doesn't mean that all recursive 
functions need to have their return values tested.

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

[toc] | [prev] | [next] | [standalone]

#75857

On Thursday, November 12, 2015 at 10:13:56 PM UTC+4, Richard Heathfield wrote:
> On 12/11/15 18:11, Alla _ wrote:
> > Of course! How could I miss that? Thank you! I have forgotten
> > that recursion requires return.
> 
> Whatever gave you that idea?
> 
> *This* recursion requires a return value to be returned and tested, 
> because it was designed that way. That doesn't mean that all recursive 
> functions need to have their return values tested.
> 
> -- 
> 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

All right. This tells me that I will see that when I do more exercises. 
Thank you! 

[toc] | [prev] | [next] | [standalone]

#75860

On 12/11/15 18:24, Alla _ wrote:
> On Thursday, November 12, 2015 at 10:13:56 PM UTC+4, Richard Heathfield wrote:
>> On 12/11/15 18:11, Alla _ wrote:
>>> Of course! How could I miss that? Thank you! I have forgotten
>>> that recursion requires return.
>>
>> Whatever gave you that idea?
>>
>> *This* recursion requires a return value to be returned and tested,
>> because it was designed that way. That doesn't mean that all recursive
>> functions need to have their return values tested.
>
> All right. This tells me that I will see that when I do more exercises.

The *really* important thing to remember about recursion is that you 
have to remember to make it stop at some point. This is normally done (I 
say "normally" because if I don't, I'm sure somebody will come up with a 
counter-example) by defining a "base case". For example, in your binary 
search algorithm the base case was that the maximum value was less than 
the minimum value. This ensured that the algorithm terminated even if 
the search key wasn't found in the array.

Without the base case (or some other way to stop the recursion), the 
recursion will proceed indefinitely... until the machine runs out of 
resources, at which point Something Drastic will happen.

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

[toc] | [prev] | [next] | [standalone]

#75869

Recursion doesn't always require return. The one example that comes to mind is the Towers of Hanoi.

[toc] | [prev] | [next] | [standalone]

#75841

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

[toc] | [prev] | [next] | [standalone]

#75856

> > // 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.
> 
No no no! Please, don't leave me ))) I am not ignoring anything.  
I forgot to mention this scanf problem this time - I should have 
written a side-note asking to ignore this exact line, as I have taken to 
doing in case I need to use this quick and dirty method. 

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

Yes. Sorry once again. 
I have now a few pages written on scanf. I am more familiar with it now.
> 
<snip>

Thank you! Yes, I see my mistake. It is the first time I was using 
recursion, and I still sometimes miss important basics.

[toc] | [prev] | [next] | [standalone]

#75859

On 12/11/15 18:23, Alla _ wrote:
>
>>> // 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.
>>
> No no no! Please, don't leave me ))) I am not ignoring anything.

Yes, you are. You are ignoring the really important task of checking 
scanf's return value to ensure that you captured some usable input.

> I forgot to mention this scanf problem this time - I should have
> written a side-note asking to ignore this exact line, as I have taken to
> doing in case I need to use this quick and dirty method.

I can't speak for other people here, but I'm going to keep on bringing 
up this issue until it's second nature to you to include the check. If 
that doesn't happen soon, it will become the *only* thing I help with, 
until such time as you are doing it correctly out of sheer frustration 
at being told off all the time.

It's for your own good, you know. :-)

<snip>

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

[toc] | [prev] | [next] | [standalone]

#75861

On Thursday, November 12, 2015 at 10:35:46 PM UTC+4, Richard Heathfield wrote:
> On 12/11/15 18:23, Alla _ wrote:
> >
> >>> // 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.
> >>
> > No no no! Please, don't leave me ))) I am not ignoring anything.
> 
> Yes, you are. You are ignoring the really important task of checking 
> scanf's return value to ensure that you captured some usable input.
> 
> > I forgot to mention this scanf problem this time - I should have
> > written a side-note asking to ignore this exact line, as I have taken to
> > doing in case I need to use this quick and dirty method.
> 
> I can't speak for other people here, but I'm going to keep on bringing 
> up this issue until it's second nature to you to include the check. If 
> that doesn't happen soon, it will become the *only* thing I help with, 
> until such time as you are doing it correctly out of sheer frustration 
> at being told off all the time.
> 
> It's for your own good, you know. :-)
> 
> <snip>

All right, no more "quick" methods. I promise. 
But that doesn't mean I will not produce zillions of stupid errors anymore )
Thank you, truly! )

[toc] | [prev] | [next] | [standalone]

#75865

On Thursday, November 12, 2015 at 12:35:46 PM UTC-6, Richard Heathfield wrote:
> Yes, you are. You are ignoring the really important task of checking 
> scanf's return value to ensure that you captured some usable input.

If one is so generous as to assume that the user won't feed scanf input that
would release nasal demons even before code returns to the calling program,
is it unreasonable to assume that the user will actually supply a number?

It's too bad C doesn't include a simple safe method which to accept a a
string from the console, return a specified leading portion in a character
array, and discard the rest, since that's one of the most common things
programs need to do; using that in conjunction with safe parsing functions
would be better than using scanf which can only be used safely in relatively
narrow cases.

[toc] | [prev] | [next] | [standalone]

#75866

On Thu, 12 Nov 2015 10:23:02 -0800 (PST), Alla _
<modelling.data@gmail.com> wrote:

You forgot the attribution line for Richard's comments

<snip>

>> Also, %i's behaviour can be unexpected to the unwary. I recommend that 
>> you use %d, as has already been explained to you before.
>
>Yes. Sorry once again. 
>I have now a few pages written on scanf. I am more familiar with it now.

If you mean you have made some personal notes about scanf to remind
you how to use it properly that is fine.  But you should still have an
accurate reference (and I get the feeling the text you are using does
not qualify).  Download n1570, the free draft of the C 2011 standard.
It is not a tutorial at all but when you need to know how to use a
complicated function like scanf it is invaluable.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#75929

On Thursday, November 12, 2015 at 11:20:17 PM UTC+4, Barry Schwarz wrote:
> On Thu, 12 Nov 2015 10:23:02 -0800 (PST), Alla _
> <modelling.data@gmail.com> wrote:
> 
> You forgot the attribution line for Richard's comments
> 
> <snip>
> 
> >> Also, %i's behaviour can be unexpected to the unwary. I recommend that 
> >> you use %d, as has already been explained to you before.
> >
> >Yes. Sorry once again. 
> >I have now a few pages written on scanf. I am more familiar with it now.
> 
> If you mean you have made some personal notes about scanf to remind
> you how to use it properly that is fine.  But you should still have an
> accurate reference (and I get the feeling the text you are using does
> not qualify).  Download n1570, the free draft of the C 2011 standard.
> It is not a tutorial at all but when you need to know how to use a
> complicated function like scanf it is invaluable.

Thank you very much. Yes, I have personal notes, and I put everything I read
here in my notebook (a physical paper one :)). I will download the standard
you are advising. I also have K&R now, therefore I have to re-read everything
yet again, from scratch ) 

[toc] | [prev] | [next] | [standalone]

#75930

On 13/11/15 07:20, Alla _ wrote:
> I also have K&R now,

Hallelujah!

> therefore I have to re-read everything
> yet again, from scratch )

It's worth it.

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

[toc] | [prev] | [next] | [standalone]

#75855

On Thursday, November 12, 2015 at 4:13:19 PM UTC, Alla _ wrote:
> Hello!
> 
> Please, take a look at the simple program that should perform
> a binary search - find a number in the sorted array based on
> binary search algorithm.
> 
Some people will tell you that you should use recursion for everything.

But a binary search isn't inherently recursive. The idea is that you have
a dictionary - words in alphabetical order. The first word is "aardvark"
and the last is "zygote" (it's a biological dictionary).
Now you want to find "chimpanzee". So you know that, if it's in the
dictionary at all, it's higher or equal to aardvark and lower or equal to zygote.
So those are your two limits.
Now take something halfway, say "monkey". Is chimpanzee equal to "monkey"?
If so, the entry is found. In fact it is lower. So replace "zygote" with "monkey"
as your upper limit. Repeat, say the next half is "goat, and the next half is
"Darwin". The next cut will give "brontosaurus". So now the lower limit has
also moved. Midway between Darwin and brontosaurus is a c- word, and
now we're closing in in it. 
You need to be a bit careful for the terminating condition, which is when
the low and the high limits come together. Make sure you don't skip it
(always test on the first and last words in the dictionary). If the low limit
is identical to the high limit and the word isn't found, it isn't in the 
dictionary.

But a binary search is normally coded as a loop, with two indices, high and low,
and a mid which equals (high + low)/2. (Again be careful when high = low +1). 

[toc] | [prev] | [next] | [standalone]

#75862

On Thursday, November 12, 2015 at 10:20:39 PM UTC+4, Malcolm McLean wrote:
> On Thursday, November 12, 2015 at 4:13:19 PM UTC, Alla _ wrote:
> > Hello!
> > 
> > Please, take a look at the simple program that should perform
> > a binary search - find a number in the sorted array based on
> > binary search algorithm.
> > 
> Some people will tell you that you should use recursion for everything.
> 
> But a binary search isn't inherently recursive. The idea is that you have
> a dictionary - words in alphabetical order. The first word is "aardvark"
> and the last is "zygote" (it's a biological dictionary).
> Now you want to find "chimpanzee". So you know that, if it's in the
> dictionary at all, it's higher or equal to aardvark and lower or equal to zygote.
> So those are your two limits.
> Now take something halfway, say "monkey". Is chimpanzee equal to "monkey"?
> If so, the entry is found. In fact it is lower. So replace "zygote" with "monkey"
> as your upper limit. Repeat, say the next half is "goat, and the next half is
> "Darwin". The next cut will give "brontosaurus". So now the lower limit has
> also moved. Midway between Darwin and brontosaurus is a c- word, and
> now we're closing in in it. 
> You need to be a bit careful for the terminating condition, which is when
> the low and the high limits come together. Make sure you don't skip it
> (always test on the first and last words in the dictionary). If the low limit
> is identical to the high limit and the word isn't found, it isn't in the 
> dictionary.
> 
> But a binary search is normally coded as a loop, with two indices, high and low,
> and a mid which equals (high + low)/2. (Again be careful when high = low +1).

Thank you! In the lecture I watched, they used an old-school yellow page 
phone book, tearing it apart and throwing away irrelevant parts. Not a 
pleasant picture to watch any book being treated like that, even if it's 
just a phone book, or even if for the best ever purpose of educating people. Maybe, such methods help millennials to visualize concepts, and hence understand them better. Anyway, yes, I understand your advice. 

[toc] | [prev] | [next] | [standalone]

#75863

On 12/11/15 18:57, Alla _ wrote:

<snip>

> In the lecture I watched, they used an old-school yellow page
> phone book, tearing it apart and throwing away irrelevant parts. Not a
> pleasant picture to watch any book being treated like that, even if it's
> just a phone book,

It's worth the cost of the book (especially as they were generally given 
away by the phone company), because it's a very graphic illustration of 
just how effective a binary search is. Even if there are a MILLION 
numbers in the book, it'll still only take twenty "chops" to get to the 
right number (or determine that it isn't there). That's not intuitive, 
but tearing up a phone book is a very graphic and memorable 
demonstration that you won't forget in a hurry.

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

[toc] | [prev] | [next] | [standalone]

#76006

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> On Thursday, November 12, 2015 at 4:13:19 PM UTC, Alla _ wrote:
>> Hello!
>>
>> Please, take a look at the simple program that should perform
>> a binary search - find a number in the sorted array based on
>> binary search algorithm.
>
> Some people will tell you that you should use recursion for
> everything.
>
> But a binary search isn't inherently recursive.  [snip]

This statement is true only in the sense that binary search isn't
inherently iterative either;  it isn't inherently one thing or
the other.  Binary search does lend itself easily to a simple
recursive implementation, and which IMO is easier to understand
than an iterative one.  If someone suggests it is "more natural"
to implement binary search iteratively than recursively, that is
just a reflection of how they are used to thinking, not anything
inherent in binary search itself.

> But a binary search is normally coded as a loop, [snip]

Only by people who are used to thinking iteratively rather than
functionally.  Someone who is used to working in both modes might
implement binary search using either recursion or iteration,
depending on other considerations.  Working in C there is no
general reason to prefer one over the other.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web