Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | pacman@kosh.dhis.org (Alan Curry) |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: A binary search algorithm that searches for an element similar to the key |
| Date | 2011-12-22 21:59 +0000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <jd0974$8vf$1@speranza.aioe.org> (permalink) |
| References | <jcr4q0$ps2$1@nnrp.ngi.it> |
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
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