Introduction to Searching

Searching is the act of locating a target value in a collection. The two foundational algorithms — linear search and binary search — make different assumptions about the data, with dramatically different costs.

Linear Search — the brute force baseline

Walk the array from left to right; compare each element to the target; stop when you find a match.

That’s the entire algorithm. Works on any data — sorted or not, numbers or strings or objects.

int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Cost

• Best case: O(1) — target is the first element.
• Worst case: O(n) — target is the last element, or not present.
• Average case: O(n / 2) = O(n).
• Space: O(1).

When linear search is actually the right answer

Don’t dismiss it. Linear search wins when:

• The data is unsorted and you have only one search to do — sorting first costs O(n log n), which is more than just scanning.
• The collection is tiny (< ~30 elements) — constant-factor overhead of binary search can make it slower in practice.
• The data is on a linked list — random access is O(n), so binary search loses its advantage.
• The data is streaming — you can only see each element once.

The Python in operator, JavaScript’s Array.indexOf, and Java’s List.contains are all linear searches under the hood.

Binary Search — O(log n) for sorted data

If the array is sorted, you can do dramatically better. Instead of checking elements one at a time, compare with the middle element and eliminate half of the remaining search space each step.

Iterative version

int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;        // avoid overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid - 1;
    }
    return -1;
}

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

public int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;        // avoid overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid - 1;
    }
    return -1;
}

Recursive version

int binarySearch(const vector<int>& arr, int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return binarySearch(arr, mid + 1, hi, target);
    else                    return binarySearch(arr, lo, mid - 1, target);
}

def binary_search(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    return binary_search(arr, target, lo, mid - 1)

public int binarySearch(int[] arr, int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return binarySearch(arr, mid + 1, hi, target);
    else                    return binarySearch(arr, lo, mid - 1, target);
}

The iterative version uses O(1) extra space; the recursive version uses O(log n) for the call stack. Both run in O(log n) time. Prefer iterative in production — same answer, less stack.

Why O(log n)?

Each iteration discards half the remaining elements. Starting with n elements, after k iterations there are n / 2^k left. We stop when n / 2^k = 1, i.e., k = log₂(n). For n = 1,000,000, that’s just 20 comparisons.

n            comparisons
-------------------------
10           ~3
1,000        ~10
1,000,000    ~20
10^9         ~30
10^18        ~60        ← the entire universe-fits-here range

This is why the difference between linear and binary search isn’t “noticeably faster” — it’s “transformatively faster on large data.”

A side-by-side comparison

Binary search is one of those algorithms where the complexity wins, but the implementation bites. Off-by-one errors are notorious. The next page introduces a unified template that eliminates them entirely.

Quick check

Next: The Binary Search Template — one piece of code, dozens of problems, zero off-by-one errors.