</>EmbeddedInterview

How does binary search work and what is the common bug?

EasyData Structures & Algorithms

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).