Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.chainon-marquant.org!nntpfeed.proxad.net!proxad.net!feeder2-2.proxad.net!nx01.iad01.newshosting.com!newshosting.com!69.16.185.16.MISMATCH!npeer02.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: Thu, 22 Dec 2011 05:56:22 -0600
Message-ID: <4EF31AE6.4E38@mindspring.com>
Date: Thu, 22 Dec 2011 06:56:22 -0500
From: pete <pfiland@mindspring.com>
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: <jcr4q0$ps2$1@nnrp.ngi.it>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 96
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.220.253
X-Trace: sv3-3hrcQmk/7ZaWMz0MfShlZvHthm4HMinimp9gQmy9ZwGVZgh95ZHPZlhGlmaX5v7GeaAUpMyFaRl8plq!XcvkB02wOBSW6B8HBO16p/6ryDzaTIUJfrIFnGQdN3AGD99YwpRcrVUWiRsqmVbzKn+sZWEB7i+2!g0iWBDGDMLQ=
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: 4082
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:14858

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