Searching

Lesson

Linear search walks every element: O(n). Binary search on sorted data: O(log n).

The standard bsearch from <stdlib.h> does the work; if you write your own, the half-open interval [lo, hi) with mid = lo + (hi-lo)/2 avoids overflow and off-by-one.

Code examples

long bsearch_int(const int *a, size_t n, int t) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] == t) return (long)mid;
        if (a[mid] < t) lo = mid + 1;
        else            hi = mid;
    }
    return -1;
}

Common mistakes

• (lo + hi) / 2 can overflow on huge inputs.
• Using binary search on unsorted data — only finds elements by accident.