There are many articles about the pedagogical benefits of writing a binary search algorithm. Instead of just implementing binary search, I wanted to take it one step furtuer. Is is possible to write a standards compliant, formally correct, and beautiful implementation of bsearch() in C?

```
// This type simplifies the
// argument list of bsearch.
typedef int (*compare_f)(
const void *x,
const void *y);
```

void *bsearch( const void *key, const void *base, size_tnel, size_twidth, compare_f compar) { size_t k; size_t lo = 0; size_t hi =nel- 1; const void *mid; while (lo <= hi) { // If we used (lo + hi)/2, then it // would overflow for large integers. // The following formula prevents that. k = lo + (hi - lo)/2;mid=base+ k*width; // If we used compar(mid, key), then it // would violate POSIX, which specifies // that key must be the first argument. int cmp = compar(key,mid); if (cmp < 0) hi = k - 1; if (cmp > 0) lo = k + 1; if (cmp == 0) return (void *)mid; } return NULL; }

Note that not every argument and variable have been colorized, just the ones that usually give people the hardest time when reasoning about this function. The average `(k)` can be reduced to `(lo + hi)/2` if the array you are handling is less than 2^{63} elements long, but since it isn't technically correct, I didn't write it that way.

## No comments:

## Post a Comment