Binary Search in C

Question

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 ?

Answer 1

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.