How does binary search work and what is the common bug?
Short answer: On a sorted array, compare the target with the middle element and discard the half that cannot contain it, repeating until found or the range is empty: O(log n). The classic bug is computing the middle as (low + high) / 2, which can overflow when indices are large; use low + (high − low) / 2. The other common bugs are mixing inclusive and exclusive bounds, which causes infinite loops or missed elements, and unsigned underflow with high = mid − 1 when mid is 0.
#include <stdio.h>
#include <stddef.h>
/* returns index of key, or -1; half-open range [lo, hi) avoids the unsigned underflow */
long bsearch_int(const int *a, size_t n, int key)
{
size_t lo = 0, hi = n;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] < key) lo = mid + 1;
else if (a[mid] > key) hi = mid;
else return (long)mid;
}
return -1;
}
/* lower bound: first index with a[i] >= key (useful for insertion points and lookup tables) */
size_t lower_bound(const int *a, size_t n, int key)
{
size_t lo = 0, hi = n;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] < key) lo = mid + 1; else hi = mid;
}
return lo;
}
int main(void)
{
int a[] = { 2, 5, 8, 12, 16, 23, 38 };
printf("%ld %ld %zu\n", bsearch_int(a, 7, 23), bsearch_int(a, 7, 7), lower_bound(a, 7, 13)); /* 5 -1 4 */
return 0;
}
Embedded uses: lookup tables (e.g. a thermistor resistance-to-temperature table, then linear interpolation between the two neighbours), finding a record in a sorted flash log, and bisection when tuning a parameter.
Variants: first/last occurrence, search in a rotated sorted array, and searching on the answer (e.g. the smallest buffer size that satisfies a condition).