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

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

A binary search algorithm that searches for an element similar to the key

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

Contents

  A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-21 00:13 +0100
    Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-21 00:14 +0000
      Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-21 06:26 -0800
        Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-21 21:04 +0000
          Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-21 23:59 -0800
            Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-22 12:02 +0000
              Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-22 05:48 -0800
                Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-22 19:24 +0000
          Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-22 00:08 -0800
            Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-22 08:49 +0000
    Re: A binary search algorithm that searches for an element similar to the key Barry Schwarz <schwarzb@dqel.com> - 2011-12-20 21:27 -0800
    Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-21 01:01 -0800
      Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-21 04:36 -0800
        Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-21 12:49 +0000
        Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-21 19:12 +0000
        Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-21 13:37 -0800
          Re: A binary search algorithm that searches for an element similar to the key gazelle@shell.xmission.com (Kenny McCormack) - 2011-12-21 23:37 +0000
          Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 11:25 -0800
            Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-27 20:13 +0000
              Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 13:25 -0800
                Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-27 22:14 +0000
                  Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 15:12 -0800
                    Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-28 00:09 +0000
                      Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 16:22 -0800
                        Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-28 03:03 +0000
              Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 13:51 -0800
                Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-27 22:14 +0000
            Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-27 14:53 -0800
        Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-23 19:45 +0100
          Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-24 06:45 +0100
            Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-24 09:52 +0100
            Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-24 16:37 +0100
              Re: A binary search algorithm that searches for an element similar to the key hopcode <hopcode@nulnulul.de> - 2011-12-24 19:11 +0100
                Re: A binary search algorithm that searches for an element similar to the key Nathan <nathancbaker@gmail.com> - 2011-12-24 12:20 -0800
        Re: A binary search algorithm that searches for an element similar to the key Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-12-28 03:21 -0800
          Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 04:01 -0800
            Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-28 18:17 +0000
              Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 16:58 -0800
                Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-29 00:43 +0000
                  Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 18:16 -0800
                    Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-28 18:28 -0800
                      Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 18:39 -0800
                        Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-28 19:00 -0800
                          Re: A binary search algorithm that searches for an element similar to the key Geoff <geoff@invalid.invalid> - 2011-12-28 22:04 -0800
                            Re: A binary search algorithm that searches for an element similar to the key pacman@kosh.dhis.org (Alan Curry) - 2011-12-29 07:50 +0000
                            Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-29 18:50 +0000
                              Re: A binary search algorithm that searches for an element similar to the key Patrick Scheible <kkt@zipcon.net> - 2011-12-29 12:52 -0800
                                Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 02:45 -0800
                                  Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-03 16:30 -0800
                          Re: A binary search algorithm that searches for an element similar to the key gazelle@shell.xmission.com (Kenny McCormack) - 2011-12-29 10:00 +0000
                      Re: A binary search algorithm that searches for an element similar to the key gazelle@shell.xmission.com (Kenny McCormack) - 2011-12-29 09:58 +0000
    Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-21 06:44 -0800
      Re: A binary search algorithm that searches for an element similar to the key John Tsiombikas <nuclear@member.fsf.org> - 2011-12-21 17:27 +0000
    Re: A binary search algorithm that searches for an element similar to  the key pete <pfiland@mindspring.com> - 2011-12-21 17:54 -0500
    Re: A binary search algorithm that searches for an element similar to the key Peter Nilsson <airia@acay.com.au> - 2011-12-21 23:09 -0800
      Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-22 00:14 -0800
      Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-22 09:50 +0100
      Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-22 18:23 +0100
    Re: A binary search algorithm that searches for an element similar to  the key pete <pfiland@mindspring.com> - 2011-12-22 06:56 -0500
    Re: A binary search algorithm that searches for an element similar to the key pacman@kosh.dhis.org (Alan Curry) - 2011-12-22 21:59 +0000
    Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-25 11:54 +0100
      Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-25 15:45 +0100
        Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-29 09:06 +0100
    Re: A binary search algorithm that searches for an element similar to the key Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 16:44 -0800

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#15153

88888 Dihedral <dihedral88888@googlemail.com> writes:
> Seebs於 2011年12月29日星期四UTC+8上午8時43分52秒寫道：
>> On 2011-12-29, 88888 Dihedral <dihedr...@googlemail.com> wrote:
>> > Seebs??? 2011???12???29????????????UTC+8??????2???17???57????????????
>> >> It's stupid because lots of programmers don't do assembly.  The test is
>> >> irrelevant.  It's like demanding that a poet be able to translate poetry
>> >> into German to prove that it's not plagiarized.
>> 
>> > I don't work with programmers don't understand BIOS and OS very often. 
>> 
>> This is yet another non-sequitur.  You don't need to be able to write
>> assembly in order to understand BIOS or OS code.  You might need to be able
>> to do a little assembly to produce a new one from scratch, but it's not
>> really a major component of most of the work going on.
>> 
>> I've done device drivers and the like, and thus far, I've only ever had to
>> mess with assembly once, when trying to debug a hardware glitch in SMP mode
>> on one particular motherboard chipset.  And even then, I didn't have to be
>> able to write assembly, just change a couple of instructions.
>
> If you are working with C++ or Java then you do not have to care about
> C or hardware, nowadays professionals in C are separated from
> professionals in C++ or Java.

Once again, you have posted a response that has nothing to do with what
you're responding to.

Let me ask you something.  Are you able to respond directly to
a question?  Yes or no.  If you can manage that, we just might be
able to get somewhere.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#15155

Keith Thompson於 2011年12月29日星期四UTC+8上午10時28分26秒寫道：
> 88888 Dihedral <dihedr...@googlemail.com> writes:
> > Seebs於 2011年12月29日星期四UTC+8上午8時43分52秒寫道：
> >> On 2011-12-29, 88888 Dihedral <dihe...@googlemail.com> wrote:
> >> > Seebs??? 2011???12???29????????????UTC+8??????2???17???57????????????
> >> >> It's stupid because lots of programmers don't do assembly.  The test is
> >> >> irrelevant.  It's like demanding that a poet be able to translate poetry
> >> >> into German to prove that it's not plagiarized.
> >> 
> >> > I don't work with programmers don't understand BIOS and OS very often. 
> >> 
> >> This is yet another non-sequitur.  You don't need to be able to write
> >> assembly in order to understand BIOS or OS code.  You might need to be able
> >> to do a little assembly to produce a new one from scratch, but it's not
> >> really a major component of most of the work going on.
> >> 
> >> I've done device drivers and the like, and thus far, I've only ever had to
> >> mess with assembly once, when trying to debug a hardware glitch in SMP mode
> >> on one particular motherboard chipset.  And even then, I didn't have to be
> >> able to write assembly, just change a couple of instructions.
> >
> > If you are working with C++ or Java then you do not have to care about
> > C or hardware, nowadays professionals in C are separated from
> > professionals in C++ or Java.
> 
> Once again, you have posted a response that has nothing to do with what
> you're responding to.
> 
> Let me ask you something.  Are you able to respond directly to
> a question?  Yes or no.  If you can manage that, we just might be
> able to get somewhere.
> 
> -- 
> Keith Thompson (The_Other_Keith) ks...@mib.org  <http://www.ghoti.net/~kst>
>     Will write code for food.
> "We must do something.  This is something.  Therefore, we must do this."
>     -- Antony Jay and Jonathan Lynn, "Yes Minister"

Did you post your binary search code here ?


I am not interested to argue with those can't contribute in this news group. 

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

#15156

88888 Dihedral <dihedral88888@googlemail.com> writes:
> Keith Thompson於 2011年12月29日星期四UTC+8上午10時28分26秒寫道：
>> 88888 Dihedral <dihedr...@googlemail.com> writes:
>> > Seebs於 2011年12月29日星期四UTC+8上午8時43分52秒寫道：
>> >> On 2011-12-29, 88888 Dihedral <dihe...@googlemail.com> wrote:
>> >> > Seebs??? 2011???12???29????????????UTC+8??????2???17???57????????????
>> >> >> It's stupid because lots of programmers don't do assembly.  The test is
>> >> >> irrelevant.  It's like demanding that a poet be able to translate poetry
>> >> >> into German to prove that it's not plagiarized.
>> >> 
>> >> > I don't work with programmers don't understand BIOS and OS very often. 
>> >> 
>> >> This is yet another non-sequitur.  You don't need to be able to write
>> >> assembly in order to understand BIOS or OS code.  You might need to be able
>> >> to do a little assembly to produce a new one from scratch, but it's not
>> >> really a major component of most of the work going on.
>> >> 
>> >> I've done device drivers and the like, and thus far, I've only ever had to
>> >> mess with assembly once, when trying to debug a hardware glitch in SMP mode
>> >> on one particular motherboard chipset.  And even then, I didn't have to be
>> >> able to write assembly, just change a couple of instructions.
>> >
>> > If you are working with C++ or Java then you do not have to care about
>> > C or hardware, nowadays professionals in C are separated from
>> > professionals in C++ or Java.
>> 
>> Once again, you have posted a response that has nothing to do with what
>> you're responding to.
>> 
>> Let me ask you something.  Are you able to respond directly to
>> a question?  Yes or no.  If you can manage that, we just might be
>> able to get somewhere.
>
> Did you post your binary search code here ?
>
> I am not interested to argue with those can't contribute in this news group. 

Thank you for answering my question, even though you didn't intend to.

*PLONK*

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#15159

On Wed, 28 Dec 2011 19:00:41 -0800, Keith Thompson <kst-u@mib.org>
wrote:

>Thank you for answering my question, even though you didn't intend to.
>
>*PLONK*

Hallelujah. I don't know what took you so long. I hope Seebs is done
too. 

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

#15160

In article <3l0of7d2q38bq570fjg7h01fo9a30u402n@4ax.com>,
Geoff  <geoff@invalid.invalid> wrote:
>On Wed, 28 Dec 2011 19:00:41 -0800, Keith Thompson <kst-u@mib.org>
>wrote:
>
>>Thank you for answering my question, even though you didn't intend to.
>>
>>*PLONK*
>
>Hallelujah. I don't know what took you so long. I hope Seebs is done
>too. 

Did you ever have a large source file, with #include misspelled as
#incldue, or a missing semicolon after a struct definition, and when you
compile it you get an error message about that, but then also a thousand
additional error messages because the compiler wouldn't give up, and
kept reading the whole thing, reporting every expression that doesn't
parse because the types are all messed up?

comp.lang.c can be like that.

Here we got a poster whose brain is missing a semicolon on line 17, but
instead of ending on that judgement, we imitate that optimistic
compiler, patiently reading the jumbled expressions and finding the
little pieces that are grammatical enough to reply to, pointing out
every mistake we can find, oblivious to the irrelevance of it all.

-- 
Alan Curry

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

#15197

On 2011-12-29, Geoff <geoff@invalid.invalid> wrote:
> Hallelujah. I don't know what took you so long. I hope Seebs is done
> too. 

I think so.  Thing is, this one's relatively good at saying things which
are vague enough that you could ALMOST think they had meaning, and were merely
confused.  Eventually you realize that it's programming horoscopes.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

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

#15210

Seebs <usenet-nospam@seebs.net> writes:

> On 2011-12-29, Geoff <geoff@invalid.invalid> wrote:
>> Hallelujah. I don't know what took you so long. I hope Seebs is done
>> too. 
>
> I think so.  Thing is, this one's relatively good at saying things which
> are vague enough that you could ALMOST think they had meaning, and were merely
> confused.  Eventually you realize that it's programming horoscopes.

Some undergrads' attempt at a program to pass the Turing Test?

-- Patrick

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

#15313

Patrick Scheible於 2011年12月30日星期五UTC+8上午4時52分35秒寫道：
> Seebs <usenet...@seebs.net> writes:
> 
> > On 2011-12-29, Geoff <geoff@invalid.invalid> wrote:
> >> Hallelujah. I don't know what took you so long. I hope Seebs is done
> >> too. 
> >
> > I think so.  Thing is, this one's relatively good at saying things which
> > are vague enough that you could ALMOST think they had meaning, and were merely
> > confused.  Eventually you realize that it's programming horoscopes.
> 
> Some undergrads' attempt at a program to pass the Turing Test?
> 
> -- Patrick

A lot people don't understand BWT and the so old  DNA sequencing problem. 

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

#15390

88888 Dihedral於 2012年1月2日星期一UTC+8下午6時45分49秒寫道：
> Patrick Scheible於 2011年12月30日星期五UTC+8上午4時52分35秒寫道：
> > Seebs <usen...@seebs.net> writes:
> > 
> > > On 2011-12-29, Geoff <geoff@invalid.invalid> wrote:
> > >> Hallelujah. I don't know what took you so long. I hope Seebs is done
> > >> too. 
> > >
> > > I think so.  Thing is, this one's relatively good at saying things which
> > > are vague enough that you could ALMOST think they had meaning, and were merely
> > > confused.  Eventually you realize that it's programming horoscopes.
> > 
> > Some undergrads' attempt at a program to pass the Turing Test?
> > 
> > -- Patrick
> 
> A lot people don't understand BWT and the so old  DNA sequencing problem.

 It is well paid to search in a set  of DNA subsequences 
for a statistical test. 

These kinds of applications in forensics are important. 

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

#15167

In article <lny5twxesm.fsf@nuthaus.mib.org>,
Keith Thompson  <kst-u@mib.org> wrote:
...
>> I am not interested to argue with those can't contribute in this news group. 
>
>Thank you for answering my question, even though you didn't intend to.
>
>*PLONK*

As District Attorney Thomson rests his case and retreats to his cave...

-- 
Faced with the choice between changing one's mind and proving that there is
no need to do so, almost everyone gets busy on the proof. 

    - John Kenneth Galbraith -

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

#15166

In article <ln39c4yuut.fsf@nuthaus.mib.org>,
Keith Thompson  <kst-u@mib.org> blubbered:
...
>Once again, you have posted a response that has nothing to do with what
>you're responding to.
>
>Let me ask you something.  Are you able to respond directly to
>a question?  Yes or no.  If you can manage that, we just might be
>able to get somewhere.

Kiks, this is not a courtroom, and you are not the District Attorney.

-- 
Religion is regarded by the common people as true,
	by the wise as foolish,
	and by the rulers as useful.

(Seneca the Younger, 65 AD)

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

#14832

   I GOT 2 TO 5 UNDER MY SUPERVISION ALL THE TIME. 

BUT ONLY 2 CAN WRITE ASSEMBLY IN THE X86 FAMILY. 

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

#14834

On 2011-12-21, 88888 Dihedral <dihedral88888@googlemail.com> wrote:
>    I GOT 2 TO 5 UNDER MY SUPERVISION ALL THE TIME. 
>
> BUT ONLY 2 CAN WRITE ASSEMBLY IN THE X86 FAMILY. 
>

How many of them can point you to the nearest caps-lock key?

-- 
John Tsiombikas
http://nuclear.mutantstargoat.com/

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

#14841 — Re: A binary search algorithm that searches for an element similar to the key

pozz wrote:
> 
> I want to write the function binsearch_low() with the same interface of
> bsearch() standard function:
> 
> void * binsearch_low (const void *key, const void *array, size_t count,
> size_t size, comparison_fn_t compare);
> 
> This function should return a pointer to the element of the array that
> is the greatest among the element with a lower value than key.  If no
> element lower than key exists, the function should return NULL.
> 
> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> function should return NULL for key=8, 10 for key=11, 12 for key=12, 20
> for key=22, 30 for key=33.
> 
> I started from a bsearch() implementation...
> 
> void *
> binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare)
> {
>    int left = 0, right = count - 1;
>    while (left <= right) {
>      const int mid = (left + right) / 2;
>      void *element = (unsigned char *)array + mid * size;
>      if (compare(key, element) > 0) left = mid + 1;
>      else if (compare(key, element) < 0) right = mid - 1;
>      else return (unsigned char *)array + mid * size;
>    }
>    return NULL;
> }
> 
> ...and arrived to the following algorithm:
> 
> void *
> binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare)
> {
>    int left = 0, right = count - 1;
>    while (left < right - 1) {
>      const int mid = (left + right) / 2;
>      void *element = (unsigned char *)array + mid * size;
>      if (compare(key, element) > 0) left = mid;
>      else if (compare(key, element) < 0) right = mid - 1;
>      else return (unsigned char *)array + mid * size;
>    }
>    if (compare(key, (unsigned char *)array + left * size) < 0) {
>      return NULL;
>    } else if (compare(key, (unsigned char *)array + right * size) >= 0) {
>      return (unsigned char *)array + right * size;
>    } else {
>      return (unsigned char *)array + left * size;
>    }
> }
> 
> Do you have any suggestions and/or improvements?

If, for the above example, 
you don't mean for the function to return NULL 
when the key is equal to 10, 
then this is what I have:

void *
losearch(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    int comp;
    size_t low, middle, high;
    const void *found = NULL;

    if (nmemb != 0) {
        const char *const array = base;   
        
        low = 0;    
        high = nmemb;
        do {
            nmemb = high - low;
            middle = nmemb / 2 + low;
            base = middle * size + array;
            comp = compar(key, base);
            if (comp > 0) {
                low = middle;
            } else {
                high = middle;
                if (comp == 0) {
                    found = base;
                } 
            }
        } while (nmemb != 1);
    }
    return (void *)found;
}

/* 
** Here is the output of a test program. 
*/


/* BEGIN b_search.c output */

int array[] = {10,10,20,20,20,30,30,40,40,40,50,50,50,50,60,60,60};
element #   :   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16

losearch(), Binary search, first key occurence matched:
10 is the value of element # 0
20 is the value of element # 2
30 is the value of element # 5
40 is the value of element # 7
50 is the value of element # 10
60 is the value of element # 14

hisearch(), Binary search, last key occurence matched:
10 is the value of element # 1
20 is the value of element # 4
30 is the value of element # 6
40 is the value of element # 9
50 is the value of element # 13
60 is the value of element # 16

/* END b_search.c output */

/*
** Here is the test program
*/



/* BEGIN b_search.c */

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#define B_SEARCH    1 /* B_SEARCH should be either 1 or 0 */
#define FUNC_ARRAY  losearch, "\n\nlosearch(), Binary search,"  \
                              " first key occurence matched:",  \
                    hisearch, "\nhisearch(), Binary search,"    \
                              " last key occurence matched:",   \
                     bsearch, "\nbsearch(), Binary search,"     \
                              " any key occurence matched:"
#define NUM_ARRAY   10,10,20,20,20,30,30,40,                    \
                    40,40,50,50,50,50,60,60,60
#define E_TYPE      int
#define STRING      "%2d"
#define NMEMB(A)    (sizeof (A) / sizeof *(A))
#define str(x)      # x
#define xstr(x)     str(x)

typedef E_TYPE      e_type;

struct lo_hi {
    void *lo;
    void *hi;
};

int comparison(const void *arg1, const void *arg2);
void *losearch(const void *key, const void *base,
               size_t nmemb, size_t size,
               int (*compar)(const void *, const void *));
void *hisearch(const void *key, const void *base,
               size_t nmemb, size_t size,
               int (*compar)(const void *, const void *));

int 
main(void)
{
    size_t index;
    e_type counter;
    e_type array[] = {NUM_ARRAY};
    e_type min = array[0];
    e_type max = array[NMEMB(array) - 1];
    struct sf {
        void *(*function)(const void *key, const void *base,
               size_t nmemb, size_t size,
               int (*compar)(const void *, const void *));
        char *string;
    } s_L[] = {FUNC_ARRAY};    
    
    puts("\n/* BEGIN b_search.c output */\n");
    fputs(xstr(E_TYPE) " array[] = {", stdout);
    for (counter = 0; NMEMB(array) > counter; ++counter) {
        printf(STRING ",", array[counter]);
    }
    fputs("\b};\nelement #   :  ", stdout);
    for (counter = 0; NMEMB(array) > counter; ++counter) {
        printf(STRING " ", counter);
    }
    for (index = 0; index != NMEMB(s_L) - !B_SEARCH; ++index) {
        puts(s_L[index].string);
        for (counter = min; max >= counter; ++counter) {
            const e_type *const found = s_L[index].function
                (&counter, array, NMEMB(array), 
                    sizeof *array, comparison);

            if (found != NULL) {
                printf(STRING " is the value of element # %d\n", 
                    *found, (int)(found - array));
            }
        }
    }    
    puts("\n/* END b_search.c output */");
    return 0;
}

int 
comparison(const void *arg1, const void *arg2)
{
    return *(e_type*)arg2  > *(e_type*)arg1 ? -1
         : *(e_type*)arg2 != *(e_type*)arg1;
}

void *
losearch(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    int comp;
    size_t low, middle, high;
    const void *found = NULL;

    if (nmemb != 0) {
        const char *const array = base;   
        
        low = 0;    
        high = nmemb;
        do {
            nmemb = high - low;
            middle = nmemb / 2 + low;
            base = middle * size + array;
            comp = compar(key, base);
            if (comp > 0) {
                low = middle;
            } else {
                high = middle;
                if (comp == 0) {
                    found = base;
                } 
            }
        } while (nmemb != 1);
    }
    return (void *)found;
}

void *
hisearch(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    int comp;
    size_t low, middle, high;
    const void *found = NULL;

    if (nmemb != 0) {
        const char *const array = base;   
        
        low = 0;    
        high = nmemb;
        do {
            nmemb = high - low;
            middle = nmemb / 2 + low;
            base = middle * size + array;
            comp = compar(key, base);
            if (0 > comp) {
                high = middle;
            } else {
                low = middle;
                if (comp == 0) {
                    found = base;
                } 
            }
        } while (nmemb != 1);
    }
    return (void *)found;
}

/* END b_search.c */

-- 
pete

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

#14849

On Dec 21, 10:13 am, pozz <pozzu...@gmail.com> wrote:
> I want to write the function binsearch_low() with the same interface of
> bsearch() standard function:
>
> void * binsearch_low (const void *key, const void *array, size_t count,
> size_t size, comparison_fn_t compare);
>
> This function should return a pointer to the element of the array that
> is the greatest among the element with a lower value than key.  If no
> element lower than key exists, the function should return NULL.

Start with a search that also returns the location where the element
is
or should be inserted.

int mbsearch(const void *key,
             const void *base,
             size_t num,
             size_t size,
             int cmp(const void *, const void *),
             size_t *where)
{
  const char *p = base;
  size_t l = 0;
  size_t u = num;

  while (l < u)
  {
    size_t m = l + (u - l) / 2;
    int c = cmp(key, p + m * size);
         if (c < 0) u = m;
    else if (0 < c) then l = m + 1;
    else { *where = m; return 1; }
  }

  *where = l;
  return 0;
}

Then your function can be done as something like...

void *pozz(const void *key,
           const void *base,
           size_t num,
           size_t size,
           int cmp(const void *, const void *))
{
  size_t *where;
  bsearch(key, base, num, size, cmp, &where);
  if (where == 0) return 0;
  return ((char *) base) + (where - 1) * size;
}

This assumes members are unique. I'll leave it to you to modify
for the case where non-unique members exist.

> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> function should return NULL for key=8, 10 for key=11, 12 for key=12,

That is different from your earler spec that required a pointer to
the largest value *lower* than the key.

--
Peter

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

#14853

On 22 Dic, 08:09, Peter Nilsson <ai...@acay.com.au> wrote:
> Start with a search that also returns the location where the element
> is
> or should be inserted.
>
> int mbsearch(const void *key,
>              const void *base,
>              size_t num,
>              size_t size,
>              int cmp(const void *, const void *),
>              size_t *where)
> {
>   const char *p = base;
>   size_t l = 0;
>   size_t u = num;
>
>   while (l < u)
>   {
>     size_t m = l + (u - l) / 2;
>     int c = cmp(key, p + m * size);
>          if (c < 0) u = m;
>     else if (0 < c) then l = m + 1;
>     else { *where = m; return 1; }
>   }
>
>   *where = l;
>   return 0;
>
> }
>
> Then your function can be done as something like...
>
> void *pozz(const void *key,
>            const void *base,
>            size_t num,
>            size_t size,
>            int cmp(const void *, const void *))
> {
>   size_t *where;
>   bsearch(key, base, num, size, cmp, &where);

I think you would have to write mbsearch.

>   if (where == 0) return 0;
>   return ((char *) base) + (where - 1) * size;
>
> }
>
> This assumes members are unique. I'll leave it to you to modify
> for the case where non-unique members exist.

Thank you for your answer and implementation.  Anyway I think the
implementation with a single function could be better.  My
binsearch_low() is very similar to your mbsearch().


> > For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> > function should return NULL for key=8, 10 for key=11, 12 for key=12,
>
> That is different from your earler spec that required a pointer to
> the largest value *lower* than the key.

You're right, I was wrong writing the specifications of the function.
I'm interested in the maximum among the elements with a lower or the
same value of the key.
In other words the function must return the pointer of the element in
the array with the same value or the immediately previous one if any,
otherwise NULL.

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

#14855

"Peter Nilsson" <airia@acay.com.au> ha scritto nel messaggio 
news:6a66a0b8-9038-4ada-94e6-3ea565cc6fab@f8g2000prm.googlegroups.com...
On Dec 21, 10:13 am, pozz <pozzu...@gmail.com> wrote:
int mbsearch(const void *key,
             const void *base,
             size_t num,
             size_t size,
             int cmp(const void *, const void *),
             size_t *where)
{
  const char *p = base;
  size_t l = 0;
  size_t u = num;

  while (l < u)
  {
    size_t m = l + (u - l) / 2;
    int c = cmp(key, p + m * size);
         if (c < 0) u = m;
    else if (0 < c) then l = m + 1;
                   ^^^^^
#io_x
#not exist then in C

    else { *where = m; return 1; }
  }

  *where = l;
  return 0;
}

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

#14867

"Peter Nilsson" <airia@acay.com.au> ha scritto nel messaggio
news:6a66a0b8-9038-4ada-94e6-3ea565cc6fab@f8g2000prm.googlegroups.com...
On Dec 21, 10:13 am, pozz <pozzu...@gmail.com> wrote:
Start with a search that also returns the location where the element
is
or should be inserted.

int mbsearch(const void *key,
             const void *base,
             size_t num,
             size_t size,
             int cmp(const void *, const void *),
             size_t *where)
{
  const char *p = base;
  size_t l = 0;
  size_t u = num;

  while (l < u)
  {
    size_t m = l + (u - l) / 2;
    int c = cmp(key, p + m * size);
         if (c < 0) u = m;
    else if (0 < c) then l = m + 1;
    else { *where = m; return 1; }
  }

  *where = l;
  return 0;
}

Then your function can be done as something like...

#io_x
#this is my only implementation of binsearch i found ['copy' from k&r2]
#someone find some error?
#but are you sure that is ok "l < u"? because K&R2 seems use "<="...
#R==return W==while
#int NmBinSer(nm*  r, nm& low, nm& high, int (*cmp)(nm*, nm&))
#{int   a;
# nm   l,h,mid;
#
# if(r==0||low>high||cmp==0)  R  0;
# l=low; h=high;
# W(l<=h){mid=(l+h)/2u; a=cmp(r,mid);
#              if(a<0) h=mid-1u;
#         else if(a>0) l=mid+1u;
#         else {*r=mid; R  1;}
#        }
# R  0;
#}

void *pozz(const void *key,
           const void *base,
           size_t num,
           size_t size,
           int cmp(const void *, const void *))
{
  size_t *where;
  bsearch(key, base, num, size, cmp, &where);
  if (where == 0) return 0;
  return ((char *) base) + (where - 1) * size;
}

This assumes members are unique. I'll leave it to you to modify
for the case where non-unique members exist.

> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> function should return NULL for key=8, 10 for key=11, 12 for key=12,

That is different from your earler spec that required a pointer to
the largest value *lower* than the key.

--
Peter

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

#14858 — Re: A binary search algorithm that searches for an element similar to the key

pozz wrote:
> 
> I want to write the function binsearch_low() with the same interface of
> bsearch() standard function:
> 
> void * binsearch_low (const void *key, const void *array, size_t count,
> size_t size, comparison_fn_t compare);
> 
> This function should return a pointer to the element of the array that
> is the greatest among the element with a lower value than key.  If no
> element lower than key exists, the function should return NULL.
> 
> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> function should return NULL for key=8, 10 for key=11, 12 for key=12, 20
> for key=22, 30 for key=33.
> 
> I started from a bsearch() implementation...
> 
> void *
> binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare)
> {
>    int left = 0, right = count - 1;
>    while (left <= right) {
>      const int mid = (left + right) / 2;
>      void *element = (unsigned char *)array + mid * size;
>      if (compare(key, element) > 0) left = mid + 1;
>      else if (compare(key, element) < 0) right = mid - 1;
>      else return (unsigned char *)array + mid * size;
>    }
>    return NULL;
> }
> 
> ...and arrived to the following algorithm:
> 
> void *
> binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare)
> {
>    int left = 0, right = count - 1;
>    while (left < right - 1) {
>      const int mid = (left + right) / 2;
>      void *element = (unsigned char *)array + mid * size;
>      if (compare(key, element) > 0) left = mid;
>      else if (compare(key, element) < 0) right = mid - 1;
>      else return (unsigned char *)array + mid * size;
>    }
>    if (compare(key, (unsigned char *)array + left * size) < 0) {
>      return NULL;
>    } else if (compare(key, (unsigned char *)array + right * size) >= 0) {
>      return (unsigned char *)array + right * size;
>    } else {
>      return (unsigned char *)array + left * size;
>    }
> }
> 
> Do you have any suggestions and/or improvements?

I don't like to see +1 or -1 in a binary search.
I admit that it is not at all important.
I rewrote it this way:


void *
binsearch_low2(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    int comp;
    size_t low, middle, high;
    const char *const array = base; 

    base = NULL;
    if (nmemb != 0 && compar(key, array) >= 0) {
        low = 0;    
        high = nmemb;
        do {
            nmemb = high - low;
            middle = nmemb / 2 + low;
            base = middle * size + array;
            comp = compar(key, base);
            if (comp > 0) {
                low = middle;
            } else {
                high = middle;
                if (comp == 0) {
                    break;
                }
            }
        } while (nmemb != 1);
    }
    return (void *)base;
}

-- 
pete

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

#14889

In article <jcr4q0$ps2$1@nnrp.ngi.it>, pozz  <pozzugno@gmail.com> wrote:
>I want to write the function binsearch_low() with the same interface of 
>bsearch() standard function:
>
>void * binsearch_low (const void *key, const void *array, size_t count, 
>size_t size, comparison_fn_t compare);
>
>This function should return a pointer to the element of the array that 
>is the greatest among the element with a lower value than key.  If no 
>element lower than key exists, the function should return NULL.

Well, everyone else is doing it, so here's my version.

It was not written in in response to this post; this is code I wrote a while
ago, and it's been in a couple of programs that actually got used.

Since it was real code, not a Usenet throwaway, I put comments in mine!

/* Like bsearch, but if there is no match, returns the highest element that
   is less than the key. (If no elements are less than key, returns NULL.)
   The extra parameter int *exact points to a flag which will be set to a
   true value if returned element compared equal to the key. */
void *le_bsearch(const void *key, const void *base, size_t nmemb,
                 size_t size, int (*compar)(const void *, const void *),
                 int *exact)
{
  size_t low;  /* lowest member that isn't known to be < key */
  size_t high; /* one plus the highest member that isn't known to be > key */

  if(nmemb==0) {
    if(exact)
      *exact=0;
    return 0;
  }

  low=0;
  high=nmemb;

  while(low<high) {
    size_t try=low+(high-low)/2;
    const void *tryp=(const char *)base+size*try;
    int cmp=compar(key, tryp);
    if(cmp<0) {
      /* try element is greater than key. So are all higher ones. */
      high=try;
    } else if(cmp>0) {
      /* try element is less than key. So are all lower ones. */
      low=try+1;
    } else {
      if(exact)
        *exact=1;
      return (void *)tryp;
    }
  }
  assert(low==high);
  if(exact)
    *exact=0;
  /* elements 0 through low-1 are known to be < key
     elements low through nmemb-1 are known to be > key
     if low==0 then no elements are < key
     if low==nmemb then no elements are > key */
  if(low==0)
    return 0;
  return (void *)((const char *)base+size*(low-1));
}

-- 
Alan Curry

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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

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

csiph-web