Searching Algorithms – Linear & Binary Search

Search for a target value in a collection.

• Linear Search – scan each element sequentially – O(n).
• Binary Search – works on sorted arrays – repeatedly halve the search interval – O(log n).

Implementation tip: Use size_t for indexes, and always check bounds.

---

📚 Binary Search (Iterative)

int binsearch(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) return (int)mid;
        else if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return -1; // not found
}