2
\$\begingroup\$

The standard C library function bsearch wasn't giving me correct results, apparently. So I decided to implement a binary searching function in place of it. It functions correctly up till now, though I haven't tested it thoroughly.

void * bsearch2(const void * base, const void * elem, const size_t nmemb, const size_t size, int (*compar)(const void *, const void *))
{
    /* Looks for elem in array. If found returns its address, else returns NULL
    Using the Binary Searching Algorithm, Assuming array to be sorted. */
    if (nmemb == 0) return NULL;

    size_t length = nmemb;
    int result;
    void * check;

    while (length > 0) {
        length = (length == 1) ? 0 : (size_t) length / 2;
        check = (void *)(base + (size * length));
        /* negative: element is greater, positive: element is smaller, zero: element is equal */
        result = compar(check, elem);
        if (result == 0)
            return check;
        if (result < 0) /* the element is in the second half */
            base = check;
    }

    return NULL;
}

Are there any drawbacks in this function that I might be overlooking ?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It seems exactly the same as the standard bsearch, with the exception that you have inverted the order of parameters in the predicate function. The standard one uses comp(key,item), yours is comp(item,key). \$\endgroup\$
    – glampert
    Oct 23, 2014 at 18:24
  • \$\begingroup\$ @glampert: Really ? Well that's great, because I wanted to see the original bsearch source code and I couldn't find it in glibc on ftp.gnu.org .. \$\endgroup\$
    – Amr Ayman
    Oct 23, 2014 at 19:21

1 Answer 1

4
\$\begingroup\$

It would be interesting to know why the bsearch() library function does not work for you, but here are some remarks to your code:

  • The initial check

    if (nmemb == 0) return NULL;
    

    is not really necessary. If nmemb is zero then the following loop will not execute at all, and the outcome is the same.

  • The cast to size_t in

    length = (length == 1) ? 0 : (size_t) length / 2;
    

    has no effect, and the conditional expression is not needed either, because 1/2 evaluates to zero. So this can be simplified to

    length = length / 2;
    
  • Arithmetic with a pointer to void as in

     check = (void *)(base + (size * length));
    

    is a GNU extension and not portable. You should replace it by

     check = (void *)((char *)base + (size * length));
    
  • In the case result < 0 you continue searching in the second half of the array including the element that was just tested. And this is actually an error, your function does not find the last element of an array with an odd number of elements. Moving base "one to the right"

    if (result < 0) { /* the element is in the second half */
        base = (void *)((char *)check + size);
    }
    

    fixes the problem.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.