Searching: Linear and Binary

Linear search: works always

int find(const int *a, int n, int t) {
    for (int i = 0; i < n; i++)
        if (a[i] == t) return i;
    return -1;
}

No preconditions. Cost: up to n comparisons.

Binary search: needs sorted data

The repeated middle test:

int bsearch_cj(const int *a, int n, int t) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;    // avoids overflow
        if (a[mid] == t) return mid;
        if (a[mid] < t) lo = mid + 1;    // target is in the RIGHT half
        else            hi = mid - 1;    // target is in the LEFT half
    }
    return -1;
}

Each iteration halves the remaining range: a million elements take ~20 steps.

The invariants that make it correct

• the target, if present, is always within [lo, hi]
• lo + (hi - lo) / 2 never overflows (unlike (lo + hi) / 2 on huge ranges)
• loop ends when lo passes hi — absence is proven, not guessed

Choosing

Unsorted data or one-off lookups → linear. Sorted data queried repeatedly → binary (sorting once costs O(n log n), then every query is nearly free).