Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4EF263C3.17C8@mindspring.com> (permalink) |
|---|---|
| Date | 2011-12-21 17:54 -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?
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
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