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 1 of 4  [1] 2 3 4  Next page →

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

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?

[toc] | [next] | [standalone]

#14812

pozz <pozzugno@gmail.com> writes:

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

Some of the problems in your come from using this as the starting
point.  It's not a particularly good model.

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

int may be too small to hold the values you need.  size_t will almost
always have a much wider range than int.  Worse, however, is the fact
that when count is zero, the initialisation will go wrong.

>   while (left < right - 1) {

If you change to using size_t, watch this - 1.

>     const int mid = (left + right) / 2;

To avoid overflow, divide both and then add.

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

This does not match your specification (and you could just have said
"return element;").

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

It would be better if the casts that are not on return statements were
to cont char * with the corresponding change to element's declaration.
Since the function does not return a pointer to const void (mirroring
bsearch) you have to break const correctness on the returns.

> Do you have any suggestions and/or improvements?

-- 
Ben.

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

#14831

On 21 Dic, 01:14, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> pozz <pozzu...@gmail.com> writes:
> > 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...
>
> Some of the problems in your come from using this as the starting
> point.  It's not a particularly good model.

Could you suggest some other 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;
>
> int may be too small to hold the values you need.  size_t will almost
> always have a much wider range than int.

Good suggestion.


> Worse, however, is the fact
> that when count is zero, the initialisation will go wrong.

count is unsigned and the operation "count - 1" is performed as
unsigned.
If count == 0, count - 1 is UINT_MAX that is not representable in a
int
variable.  Is this the problem?


> >   while (left < right - 1) {
>
> If you change to using size_t, watch this - 1.

I changed to:
  while (right - left > 1) {

> >     const int mid = (left + right) / 2;
>
> To avoid overflow, divide both and then add.

Do you suggest to write

  const int mid = left / 2 + right / 2;

?  I think it doesn't always work.  If left is 5 and right is 7, mid
should be 6, but 5/2 + 7/2 = 5.


> >     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;
>
> This does not match your specification (and you could just have said
> "return element;").

I was wrong writing the specifications.  The correct specification is:

"This function should return a pointer to the element of the array
that
is the greatest among the elements with a lower or the same value as
the
key.  If no element lower than key exists, the function should return
NULL."


> >   }
> >   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;
> >   }
> > }
>
> It would be better if the casts that are not on return statements were
> to cont char * with the corresponding change to element's declaration.
> Since the function does not return a pointer to const void (mirroring
> bsearch) you have to break const correctness on the returns.

Why should I cast array to (const char *)?

This is my last implementation:

void *
binsearch_low (const void *key, const void *array, size_t count,
  size_t size, comparison_fn_t compare)
{
  if (count) {
    size_t left = 0;
    size_t right = count - 1;
    while (right - left > 1) {
      const int mid = (left + right) / 2;
      const 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 (void *)element;
    }
    if (compare(key, (const char *)array + left * size) < 0) {
      return NULL;
    } else if (compare(key, (const char *)array + right * size) >= 0)
{
      return (unsigned char *)array + right * size;
    } else {
      return (unsigned char *)array + left * size;
    }
  }
  return NULL;
}

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

#14837

pozz <pozzugno@gmail.com> writes:

> On 21 Dic, 01:14, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> pozz <pozzu...@gmail.com> writes:
>> > 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...
>>
>> Some of the problems in your come from using this as the starting
>> point.  It's not a particularly good model.
>
> Could you suggest some other implementation?

Sorry, I don't know anything off hand.

<snip>
>> > ...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;
>>
>> int may be too small to hold the values you need.  size_t will almost
>> always have a much wider range than int.
>
> Good suggestion.
>
>> Worse, however, is the fact
>> that when count is zero, the initialisation will go wrong.
>
> count is unsigned and the operation "count - 1" is performed as
> unsigned.
> If count == 0, count - 1 is UINT_MAX that is not representable in a
> int variable.  Is this the problem?

That's half of it.  If it's not representable you get whatever the
implementation decides to do (which can include raising an exception)
but if it *is* representable as int, you get a value that will probably
cause all sorts of grief later on.

<snip>
>> >     const int mid = (left + right) / 2;
>>
>> To avoid overflow, divide both and then add.
>
> Do you suggest to write
>
>   const int mid = left / 2 + right / 2;
>
> ?  I think it doesn't always work.  If left is 5 and right is 7, mid
> should be 6, but 5/2 + 7/2 = 5.

I think it can be made to work for binary search, but you are right that
in your case it does not because you want to set low == mid when you
advance low.  There are probably lots of ways round this, but the
crudest is to mirror your original expression.  Maybe

  (left + right&1)/2 + 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;
<snip>
>> >   }
>> >   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;
>> >   }
>> > }
>>
>> It would be better if the casts that are not on return statements were
>> to cont char * with the corresponding change to element's declaration.
>> Since the function does not return a pointer to const void (mirroring
>> bsearch) you have to break const correctness on the returns.
>
> Why should I cast array to (const char *)?

I like to be told when I "cast away const" so preserving it when
possible reduces the number of warnings.  Also, it is some very simple
sense the right thing to do!

> This is my last implementation:
>
> void *
> binsearch_low (const void *key, const void *array, size_t count,
>   size_t size, comparison_fn_t compare)
> {
>   if (count) {
>     size_t left = 0;
>     size_t right = count - 1;
>     while (right - left > 1) {

This still goes wrong when count == 0.  I would keep 'right' one bigger
than you do and adjust the rest of the code accordingly.

>       const int mid = (left + right) / 2;
>       const 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 (void *)element;
>     }
>     if (compare(key, (const char *)array + left * size) < 0) {
>       return NULL;
>     } else if (compare(key, (const char *)array + right * size) >= 0)
> {
>       return (unsigned char *)array + right * size;
>     } else {
>       return (unsigned char *)array + left * size;
>     }
>   }
>   return NULL;
> }

-- 
Ben.

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

#14851

On 21 Dic, 22:04, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> pozz <pozzu...@gmail.com> writes:
[...]
> > void *
> > binsearch_low (const void *key, const void *array, size_t count,
> >   size_t size, comparison_fn_t compare)
> > {
> >   if (count) {
> >     size_t left = 0;
> >     size_t right = count - 1;
> >     while (right - left > 1) {
>
> This still goes wrong when count == 0.

If count == 0, the execution skip after the if() statement and goes
directly to

  return NULL;

I think it works as I wrote.

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

#14859

pozz <pozzugno@gmail.com> writes:

> On 21 Dic, 22:04, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> pozz <pozzu...@gmail.com> writes:
> [...]
>> > void *
>> > binsearch_low (const void *key, const void *array, size_t count,
>> >   size_t size, comparison_fn_t compare)
>> > {
>> >   if (count) {
>> >     size_t left = 0;
>> >     size_t right = count - 1;
>> >     while (right - left > 1) {
>>
>> This still goes wrong when count == 0.
>
> If count == 0, the execution skip after the if() statement and goes
> directly to
>
>   return NULL;
>
> I think it works as I wrote.

If count is 0, right == SIZE_MAX so right - left is greater than 1 and
into the loop we go.  There we will try to access array[SIZE_MAX/2].

-- 
Ben.

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

#14860

On 22 Dic, 13:02, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> pozz <pozzu...@gmail.com> writes:
> > On 21 Dic, 22:04, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> >> pozz <pozzu...@gmail.com> writes:
> > [...]
> >> > void *
> >> > binsearch_low (const void *key, const void *array, size_t count,
> >> >   size_t size, comparison_fn_t compare)
> >> > {
> >> >   if (count) {
> >> >     size_t left = 0;
> >> >     size_t right = count - 1;
> >> >     while (right - left > 1) {
>
> >> This still goes wrong when count == 0.
>
> > If count == 0, the execution skip after the if() statement and goes
> > directly to
>
> >   return NULL;
>
> > I think it works as I wrote.
>
> If count is 0, right == SIZE_MAX so right - left is greater than 1 and
> into the loop we go.  There we will try to access array[SIZE_MAX/2].

If count is 0 I go directly to return NULL, skipping if statements.

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

#14876

pozz <pozzugno@gmail.com> writes:

> On 22 Dic, 13:02, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> pozz <pozzu...@gmail.com> writes:
>> > On 21 Dic, 22:04, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> >> pozz <pozzu...@gmail.com> writes:
>> > [...]
>> >> > void *
>> >> > binsearch_low (const void *key, const void *array, size_t count,
>> >> >   size_t size, comparison_fn_t compare)
>> >> > {
>> >> >   if (count) {
>> >> >     size_t left = 0;
>> >> >     size_t right = count - 1;
>> >> >     while (right - left > 1) {
>>
>> >> This still goes wrong when count == 0.
>>
>> > If count == 0, the execution skip after the if() statement and goes
>> > directly to
>>
>> >   return NULL;
>>
>> > I think it works as I wrote.
>>
>> If count is 0, right == SIZE_MAX so right - left is greater than 1 and
>> into the loop we go.  There we will try to access array[SIZE_MAX/2].
>
> If count is 0 I go directly to return NULL, skipping if statements.

Yes, of course.  I missed the if.  I missed it, in part because it seems
like an odd thing to do, but it's certainly correct.

-- 
Ben.

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

#14852

On 21 Dic, 22:04, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
[...]
> >> >     const int mid = (left + right) / 2;
>
> >> To avoid overflow, divide both and then add.

I tried with this...

  size_t left, right, mid;
  if (sizeof(size_t) == 4) {
    right = left = 0xFFFFFFFFU;
    mid = (left + right) / 2;
    if (mid == 0x7FFFFFFFU) printf("4: OK\n");
  } else if (sizeof(size_t) == 2) {
    right = left = 0xFFFFU;
    mid = (left + right) / 2;
    if (mid == 0x7FFFU) printf("2: OK\n");
  }

...and it prints "4: OK", so it seems there wasn't overflow.  Isn't it
guaranteed by the standard?

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

#14857

On 2011-12-22, pozz <pozzugno@gmail.com> wrote:
> I tried with this...

>   size_t left, right, mid;
>   if (sizeof(size_t) == 4) {

Right here you are being silly.  Don't do this.

I don't know why you keep doing this.  Rather than writing something
which is correct on any system, you seem to go out of your way to find
new ways to test for specific systems when they don't matter.

>     right = left = 0xFFFFFFFFU;
>     mid = (left + right) / 2;
>     if (mid == 0x7FFFFFFFU) printf("4: OK\n");
>   } else if (sizeof(size_t) == 2) {
>     right = left = 0xFFFFU;
>     mid = (left + right) / 2;
>     if (mid == 0x7FFFU) printf("2: OK\n");
>   }

> ...and it prints "4: OK", so it seems there wasn't overflow.  Isn't it
> guaranteed by the standard?

This test doesn't even come close to proving what you think it proves.  Here's
the thing.  Let's ignore all the gratuitous portability problems and imagine
that size_t is 32 bits and has a max of 0xFFFFFFFF.  Now, if you do the math,
you'll note:
	0xFFFFFFFF + 0xFFFFFFFF = 0xFFFFFFFE.  Divide that by two, and
you get 0x7FFFFFFF.  Okay, but...

Is that between them?

The goal here is to get a value which is the average of left and right.
Let's make it a bit easier to see.

Let's use:
	left =  0xF0000001;
	right = 0xF0000003;

The number we want, the average between them, is clearly 0xF0000002.  But
what do we get?  Well, we probably get (0xE0000004 / 2), which comes out as
0x70000002.

You just carefully wrote a program which proves that there is in fact
overflow, and you're not handling it.

Consider, as an alternative:

	mid = ((right - left) / 2) + left;

for size_t, we know that left and right are both always positive, and the
algorithm guarantees that right is never smaller than left.  This will
always give you a value between left and right (or, if they're exactly
one apart, equal to left), and will never overflow, and doesn't depend
on guesswork as to the range of size_t.  (And there are real systems with
size_t being 8 bytes, which is yet another flaw.)

General Rule:  If you are writing logic which uses sizeof() to guess range,
you are almost certainly doing it wrong.

Also, stop and sanity-check your answers.  How on earth do you conclude that
7FFFFFFF is the average of two numbers larger than itself?

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

#14815

On Wed, 21 Dec 2011 00:13:05 +0100, 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.
>
>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.

Based on you description, it should return &array[0] for key=11, etc.
You are expecting a pointer, not the value the pointer points to.

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

This will return a pointer to the array element that matches key. Your
requirement specifically stated you wanted an element that was less
than key.  You probably want to change the else if to <= and delete
this else.

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

Again, if compare returns 0 you return the address of an element that
matches key instead of one that is less than key.

>   } else {
>     return (unsigned char *)array + left * size;
>   }
>}
>
>Do you have any suggestions and/or improvements?

-- 
Remove del for email

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

#14821

On Wednesday, December 21, 2011 7:13:05 AM UTC+8, 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;
mid is a variable

>      void *element = (unsigned char *)array + mid * size;
element is a pointer that stores address
>      if (compare(key, element) > 0) left = mid + 1;
*element is of type unsigned char but element is of type void * 
 
>      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?

kind of lousy for  programs that mix a pointer declared and
the type that a pointer points to 

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

#14825

I wrote a binary search in assembly in 386 20 years ago.

This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6 
32 bit general registers and a stack that can be pushed and popped. 

I suggest you store the array starting address  in ESI and use EDI as a general 
pointer in the heap.  

A program in C code within 20 lines should be coded in assembly easily for professionals in any 32 bit cpu easily. 

I'll warn  any programmer that  dare to use  any lousy name of any variable
to be a pointer witout ptr* or p* in the name  under my  supervision.


Then I'll ask the programmer to convert the program into a specified assembly
to  prove the programmer is not stealing codes form others and faking to be 
his own works. 
 
 

 

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

#14827

88888 Dihedral <dihedral88888@googlemail.com> writes:

> I wrote a binary search in assembly in 386 20 years ago.
>
> This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6 
> 32 bit general registers and a stack that can be pushed and popped. 
>
> I suggest you store the array starting address in ESI and use EDI as a
> general pointer in the heap.
>
> A program in C code within 20 lines should be coded in assembly easily
> for professionals in any 32 bit cpu easily.
>
> I'll warn  any programmer that  dare to use  any lousy name of any variable
> to be a pointer witout ptr* or p* in the name  under my  supervision.

How many programmers are there under your supervision?

> Then I'll ask the programmer to convert the program into a specified assembly
> to  prove the programmer is not stealing codes form others and faking to be 
> his own works. 

-- 
Ben.

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

#14835

On 2011-12-21, 88888 Dihedral <dihedral88888@googlemail.com> wrote:
> A program in C code within 20 lines should be coded in assembly
> easily for professionals in any 32 bit cpu easily.

I'm guessing you haven't used all that many 32-bit CPUs.

> Then I'll ask the programmer to convert the program into a specified assembly
> to  prove the programmer is not stealing codes form others and faking to be 
> his own works. 

Er, why?

FWIW, I have only enough knowledge of various assembly languages to read
simple stuff in them.  Can't write any, never had a need to.  It's not one
of the most relevant skills these days.

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

#14838

88888 Dihedral <dihedral88888@googlemail.com> writes:
[...]
> A program in C code within 20 lines should be coded in assembly easily
> for professionals in any 32 bit cpu easily.

But why on Earth would anyone want to waste the time doing so?

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

#14843

In article <ln7h1p38tm.fsf@nuthaus.mib.org>,
Keith Thompson  <kst-u@mib.org> wrote:
>88888 Dihedral <dihedral88888@googlemail.com> writes:
>[...]
>> A program in C code within 20 lines should be coded in assembly easily
>> for professionals in any 32 bit cpu easily.
>
>But why on Earth would anyone want to waste the time doing so?

Why do you waste your time spewing your venom (posting) here?

Really, it's the same question - same basic answer.  The answer is: Because
it makes you feel good and you have the time to waste.

As do I.

-- 
They say compassion is a virtue, but I don't have the time!

    - David Byrne -

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

#15036

Keith Thompson於 2011年12月22日星期四UTC+8上午5時37分25秒寫道：
> 88888 Dihedral <dihedr...@googlemail.com> writes:
> [...]
> > A program in C code within 20 lines should be coded in assembly easily
> > for professionals in any 32 bit cpu easily.
> 
> But why on Earth would anyone want to waste the time doing so?
> 
> -- 
> 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"

I love those jobs that ordinary low paid programmers can't do
that is how I got paid well. It  is  not the  language used but just 
the difficulties and talents required to complete tough tasks 
to get the rewards must be rare.

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

#15041

On 2011-12-27, 88888 Dihedral <dihedral88888@googlemail.com> wrote:
> I love those jobs that ordinary low paid programmers can't do
> that is how I got paid well.

If your code and writing is any indication, this is a terrifying concept.

> It  is  not the  language used but just 
> the difficulties and talents required to complete tough tasks 
> to get the rewards must be rare.

Huh.  I would much rather put the hard work into building a robust and
maintainable design such that the skills needed to keep it running aren't
rare.

The goal here is not to show off, it's to do the best work possible.
Maintainable code is better than flashy code.

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

#15043

Seebs於 2011年12月28日星期三UTC+8上午4時13分54秒寫道：
> On 2011-12-27, 88888 Dihedral <dihedr...@googlemail.com> wrote:
> > I love those jobs that ordinary low paid programmers can't do
> > that is how I got paid well.
> 
> If your code and writing is any indication, this is a terrifying concept.
> 
> > It  is  not the  language used but just 
> > the difficulties and talents required to complete tough tasks 
> > to get the rewards must be rare.
> 
> Huh.  I would much rather put the hard work into building a robust and
> maintainable design such that the skills needed to keep it running aren't
> rare.
> 

We don't have to argue about chief technical officer's views
and chief financial officer's views.  

CTO and CFO normally think quite differently. 





> The goal here is not to show off, it's to do the best work possible.
> Maintainable code is better than flashy code.
> 
> -s
> -- 
> Copyright 2011, all wrongs reversed.  Peter Seebach / usenet...@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]

Page 1 of 4  [1] 2 3 4  Next page →

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

csiph-web