Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4EF31AE6.4E38@mindspring.com> (permalink) |
|---|---|
| Date | 2011-12-22 06:56 -0500 |
| From | pete <pfiland@mindspring.com> |
| Organization | PF |
| Newsgroups | comp.lang.c |
| Subject | Re: A binary search algorithm that searches for an element similar to the key |
| References | <jcr4q0$ps2$1@nnrp.ngi.it> |
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
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web