# Binary Search in C

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 ?

• 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). Oct 23 '14 at 18:24
• @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 .. Oct 23 '14 at 19:21

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.