Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!goblin3!goblin1!goblin.stu.neva.ru!postnews.google.com!news2.google.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Wed, 21 Dec 2011 16:55:00 -0600 Message-ID: <4EF263C3.17C8@mindspring.com> Date: Wed, 21 Dec 2011 17:54:59 -0500 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: A binary search algorithm that searches for an element similar to the key References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 281 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.223.147 X-Trace: sv3-1WVfXEWD5wzkDWrOrvX0lWisz9k/7tUxrHDSo54rDHTibCtlFwXTcnS9IvR6LxA+ubxp1sQmJfdKwl2!x+R1u8yRemY/c+tm+Fo5MrxweP1fsyrSAahT2NjGmXEFTeSzaHfogevf5wjulsxF2pgcZTDEUTUP!hjk/5e5Hjx8= X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 9307 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:14841 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 #include #include #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