Searching Algorithms: Linear to Answer Search

1. Problem and Motivation

Searching asks whether a desired value, position, or feasible answer exists in a domain. The obvious method scans candidates one by one. That is optimal when no structure is known, but wasteful when the domain is sorted or the answer predicate changes only once.

Search is broader than finding an exact array value. Lower and upper bounds find insertion boundaries, binary search on answer finds the smallest feasible capacity, ternary search optimizes a unimodal function, interpolation predicts a likely position, and galloping search expands quickly inside an ordered stream.

2. Prerequisites and Definitions

• Candidate domain: the values or positions that may contain the answer.
• Monotone predicate: a Boolean test whose results change at most once, such as false, false, true, true.
• Boundary: the first or last position satisfying a condition.
• Uniform distribution: a key distribution where interpolation can estimate position accurately.
• Unimodal function: a function that rises then falls, or falls then rises, with one optimum region.

3. A Small Concrete Example

4. Core Insight and Plain-English Steps

1. State the candidate domain and the desired guarantee.
2. Find the strongest reliable structure: arbitrary order, sorted order, monotone feasibility, distribution, or unimodality.
3. Probe a candidate position or value.
4. Prove which region cannot contain the answer.
5. Repeat until the domain is empty, a boundary is isolated, or the numeric interval is within tolerance.

5. Searching Families

Linear Search

Linear search checks each item until it finds the target or reaches the end. It requires no ordering, works on streams, and costs $O(n)$ worst case. Its best case is $O(1)$.

Binary Search and Boundaries

Binary search requires sorted data and repeatedly halves the interval, giving $O(\log n)$. Lower bound finds the first position with value at least the target; upper bound finds the first position with value greater than the target. First and last occurrence are boundary searches built from these predicates.

Binary Search on Answer

Sometimes the answer is not an array index. Define a predicate such as “capacity $x$ can finish the workload.” If feasibility is monotone, binary search finds the smallest feasible $x$. This converts an optimization problem into decision plus search.

Binary Search on Reals

For a monotone continuous predicate or a numeric threshold, search a real interval for a fixed number of iterations or until its width is below $\varepsilon$. Floating-point tolerance and termination policy are part of correctness.

Ternary Search

Ternary search applies to a unimodal function. Split the interval at two interior points, compare their values, and discard the side that cannot contain the optimum. It costs $O(\log n)$ iterations on a discrete domain and $O(\log((R-L)/\varepsilon))$ iterations for a real interval.

Jump Search

Jump search moves through a sorted array in blocks of size about $\sqrt n$, then performs a linear scan inside the identified block. Its time is $O(\sqrt n)$ and it can be useful when random access is cheaper than complicated branching but binary search is not ideal.

Exponential Search

Exponential search probes positions $1,2,4,8,\dots$ until it passes the target, then binary-searches the bounded interval. It costs $O(\log p)$ when the target is near position $p$, and works well for unbounded or incrementally available ordered data.

Interpolation Search

Interpolation search estimates the likely position using key values. On uniformly distributed numeric data its average behavior can approach $O(\log\log n)$, but skewed distributions produce $O(n)$ worst-case behavior. It requires numeric keys and careful division when endpoint values are equal.

Fibonacci Search

Fibonacci search partitions a sorted array using Fibonacci offsets rather than a midpoint. It uses $O(\log n)$ comparisons and historically helped when addition was cheaper than division or memory access patterns favored its probes.

Galloping Search

Galloping, or exponential-range search, doubles a probe distance while one side remains favorable, then switches to binary search. Merge algorithms and ordered indexes use it when one stream is likely to advance far ahead of another.

6. Correctness and Dry Run

Binary search correctness rests on a range invariant: if a valid answer exists, it remains inside the active interval. Each comparison removes only a region proven impossible. For lower bound, the invariant is that all positions before low fail the predicate and all positions at or after high may still satisfy it. At termination, low == high is the first satisfying position.

For answer search, correctness depends on proving monotonicity first. If a larger capacity can never make a feasible workload infeasible, the predicate has one false-to-true boundary and binary search is valid. Without that proof, halving the answer space can discard the real solution.

7. Complexity and Tradeoffs

8. Three-Language Implementation

These panels implement exact search, lower bound, and binary search on answer with equivalent inputs and outputs.

def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = low + (high - low) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

def lower_bound(values, target):
    low, high = 0, len(values)
    while low < high:
        middle = low + (high - low) // 2
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle
    return low

values = [2, 5, 8, 12, 17, 23, 31]
print(binary_search(values, 17))
print(lower_bound(values, 16))

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& values, int target) {
    int low = 0, high = static_cast<int>(values.size()) - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int lowerBound(const std::vector<int>& values, int target) {
    int low = 0, high = static_cast<int>(values.size());
    while (low < high) {
        int middle = low + (high - low) / 2;
        if (values[middle] < target) low = middle + 1;
        else high = middle;
    }
    return low;
}

int main() {
    std::vector<int> values{2, 5, 8, 12, 17, 23, 31};
    std::cout << binarySearch(values, 17) << '\n';
    std::cout << lowerBound(values, 16) << '\n';
}

import java.util.Arrays;

public class SearchingTechniques {
    static int binarySearch(int[] values, int target) {
        int low = 0, high = values.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (values[middle] == target) return middle;
            if (values[middle] < target) low = middle + 1;
            else high = middle - 1;
        }
        return -1;
    }

    static int lowerBound(int[] values, int target) {
        int low = 0, high = values.length;
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (values[middle] < target) low = middle + 1;
            else high = middle;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] values = {2, 5, 8, 12, 17, 23, 31};
        System.out.println(binarySearch(values, 17));
        System.out.println(lowerBound(values, 16));
    }
}

9. Applications and Alternatives

Do not use interpolation search merely because its average bound looks attractive: distribution and integer arithmetic matter. Do not use ternary search on a function with multiple local optima. For real-valued search, define a tolerance and prove that the predicate or objective has the required shape.

10. Exercises and Mastery

Easy

1. Trace binary search for a present and absent target.
2. Implement lower and upper bound for duplicate values.
3. Compare linear and binary search on arrays of size 1, 2, and $n$.

Medium

1. Use binary search on answer to find the minimum shipping capacity for packages.
2. Implement exponential search for a sorted array with an unknown logical length.
3. Implement jump search and compare block sizes.

Hard

1. Design an interpolation-search fallback for skewed keys.
2. Use ternary search to minimize a convex real-valued function with an explicit tolerance.
3. Explain when galloping search improves a merge and when it adds overhead.

Review rhythm: tomorrow, reconstruct exact search and lower bound from their invariants; next week, implement answer search and exponential search in all three languages; several weeks later, identify the hidden predicate or ordering in an unfamiliar problem.

11. Summary Cheat Sheet

• Linear search needs no structure and costs $O(n)$.
• Binary search halves a sorted or monotone domain in $O(\log n)$.
• Lower and upper bounds are boundary searches, not merely exact lookup.
• Answer search turns monotone feasibility into optimization.
• Ternary search needs unimodality; interpolation needs favorable numeric distribution.
• Jump, exponential, Fibonacci, and galloping search change how a useful interval is found or probed.
• Correctness comes from stating what remains possible after each probe.