Lesson 2 · Core algorithms

Searching Algorithms

Searching is the problem of locating an item or a boundary. Which method is available depends on what the data guarantees: an unsorted sequence allows only a scan, sorted data unlocks halving, and auxiliary structures trade memory and build time for faster lookup.

Linear search is the baseline

A scan needs no preprocessing and works on any sequence, so O(N) can be optimal when data is unsorted and queried once. It also establishes the correctness baseline against which every optimized method should be tested.

Repeated queries change the economics. Sorting once or building an index may justify its upfront cost when many later lookups become logarithmic or expected constant time.

One unsorted query: scan
Many ordered queries: sort, then binary search
Key membership: consider a hash set

Binary search needs sorted data

When a sequence is sorted, each comparison can discard half of what remains, giving O(log N). This is the largest win available to searching, but it is only legal when order is guaranteed and the structure supports random access.

Because its invariant and boundary cases deserve full treatment, binary search has a lesson of its own.

Requires sorted, randomly accessible data
O(log N) time and O(1) extra space
See the Binary Search lesson for the invariant

Key reference

Terms, operations, and practical uses

Search vocabulary

TargetThe value or condition being located.
Search intervalThe region that is still capable of containing the answer.
Monotonic predicateA yes/no condition that changes direction at most once across an ordered domain.

Binary-search boundaries

Lower boundThe first position whose value is at least the target.
Upper boundThe first position whose value is greater than the target.
MidpointThe inspected position that proves which portion can be discarded.

Choose the right search

Linear searchNeeds no preprocessing and works on unsorted data.
Hash lookupProvides expected constant-time membership by maintaining an auxiliary index.
Answer-space searchBinary-searches possible results when feasibility changes monotonically.

Code example

Find 16 with binary search

def binary_search(values, target):
    left, right = 0, len(values) - 1
    while left <= right:
        middle = left + (right - left) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1
print('index', binary_search([2, 5, 8, 12, 16, 21, 29], 16))

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

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

Input[2, 5, 8, 12, 16, 21, 29], target 16

Outputindex 4

Example

Run the example step by step

Output

Hash lookup trades memory for speed

A hash table computes a bucket index directly from the key, giving expected O(1) membership and retrieval without requiring any order. The cost is extra memory, no ordering, and a worst case that degrades when many keys collide into one bucket.

Use hashing when the question is membership or key-to-value retrieval. It cannot answer range or nearest-value questions.

Expected O(1), worst case O(N)
Answers membership, not ordering
Needs a good hash and a low load factor

Tree search keeps order available

A balanced binary search tree answers lookups in O(log N) like binary search, but also supports insertion and deletion in the same bound while keeping keys ordered. That makes range queries and in-order traversal possible, which hashing cannot do.

Choose a tree when the data changes and order still matters.

O(log N) search, insert, and delete
Keeps keys in sorted order
Supports range and successor queries