📈 Algorithms & Complexity

Searching: linear vs binary

⏱ 13 min · free interactive lesson · quizzes, visualizations & a real compiler

You have an array of n values and you want to know: is 23 in there, and where? This tiny problem is the perfect first arena for last lesson's Big-O ideas, because two correct solutions to it differ so dramatically that one takes a million steps where the other takes twenty.

Linear search: the honest baseline

No assumptions, no tricks: walk the array front to back and compare. It works on any array, sorted or not, and it's the best you can possibly do when the data is unordered — the target could hide anywhere, so you must be prepared to look everywhere.

▶ This spot has an interactive arrayviz widget — open the interactive lesson to play with it.

#include <stdio.h>

int linear_search(const int *a, int n, int target) {
    for (int i = 0; i < n; i++)
        if (a[i] == target)
            return i;         /* index of the first hit      */
    return -1;                /* checked all n — not here    */
}

int main(void) {
    int a[] = {14, 3, 92, 41, 7, 66, 25, 58};
    printf("7   is at index %d\n", linear_search(a, 8, 7));
    printf("100 is at index %d\n", linear_search(a, 8, 100));
    return 0;
}

$ gcc linear.c -o linear && ./linear
7   is at index 4
100 is at index -1

Worst case (target absent or last): n comparisons — Θ(n). Average for a present target: about n/2, which is still Θ(n) after dropping the ½.

Binary search: halve or die

Now add one precondition — the array is sorted — and everything changes. Check the middle element. Too small? The target can only be in the right half. Too big? Left half. Either way, one comparison destroys half the remaining candidates. Watch the gray (eliminated) region grow:

▶ This spot has an interactive arrayviz widget — open the interactive lesson to play with it.

#include <stdio.h>

int binary_search(const int *a, int n, int target) {
    int lo = 0, hi = n - 1;         /* inclusive bounds       */
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   /* overflow-safe!     */
        if (a[mid] == target) return mid;
        if (a[mid] < target)  lo = mid + 1;  /* discard left  */
        else                  hi = mid - 1;  /* discard right */
    }
    return -1;
}

int main(void) {
    int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    printf("23 is at index %d\n", binary_search(a, 10, 23));
    printf("7  is at index %d\n", binary_search(a, 10, 7));
    return 0;
}

$ gcc binary.c -o binary && ./binary
23 is at index 5
7  is at index -1

Watching the bounds — where the bugs live

Binary search is famously easy to get almost right. Studies found most programmers' first attempts had off-by-one bugs: < vs <= in the loop condition, or forgetting the +1/−1 when shrinking. Step through a correct one and watch lo and hi pincer the target:

▶ This spot has an interactive trace widget — open the interactive lesson to play with it.

n vs log n — the payoff

Halving means the number of comparisons is log₂ n. A million elements? log₂(1,000,000) ≈ 20. A billion? 30. Doubling the data adds one comparison:

▶ This spot has an interactive bigo widget — open the interactive lesson to play with it.

Don't write it — call it: bsearch

The C standard library ships a generic binary search in <stdlib.h>. Like qsort, it works on any element type via a comparison callback:

#include <stdio.h>
#include <stdlib.h>

int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa, b = *(const int *)pb;
    return (a > b) - (a < b);   /* -1, 0, +1 */
}

int main(void) {
    int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int key = 23;

    int *hit = bsearch(&key, a, 10, sizeof a[0], cmp_int);
    if (hit) printf("found %d at index %td\n", *hit, hit - a);
    else     printf("not found\n");
    return 0;
}

$ gcc use_bsearch.c -o use_bsearch && ./use_bsearch
found 23 at index 5
# bsearch returns a POINTER to the element (or NULL);
# subtract the array base to recover the index.

▶ This spot has an interactive editor widget — open the interactive lesson to play with it.

Binary search demands sorted data — so the obvious next question is: how does data get sorted, and what does that cost?