Searching Algorithms

Also Known As

TL;DR

Explanation

Linear search: scan each element — O(n), works on unsorted data, unavoidable for some problems. Binary search: halve the search space each step — O(log n), requires sorted data. Finding the midpoint: mid = left + (right - left) / 2 (avoids integer overflow). Binary search applications: finding a value in a sorted array, searching a monotonic function, lower/upper bounds. Hash lookup (PHP array, SplHashMap): O(1) average — best for repeated lookups. For database queries, indexes implement B-tree search (O(log n)).

Diagram

flowchart LR
    subgraph Linear Search O of n
        ARR1[3 7 1 9 4 6 2] -->|scan each| FOUND1[Found 9<br/>at index 3]
    end
    subgraph Binary Search O of log n - sorted only
        ARR2[1 2 3 4 6 7 9<br/>mid=4] -->|target > mid| RIGHT[6 7 9<br/>mid=7] -->|target > mid| FOUND2[Found 9]
    end
    subgraph Hash Lookup O of 1
        KEY[key: 9] --> HASH[hash function<br/>bucket 3] --> VAL[value directly]
    end
    style FOUND1 fill:#d29922,color:#fff
    style FOUND2 fill:#238636,color:#fff
    style VAL fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Binary search on unsorted data — produces wrong results silently.
• Not using array_flip() for repeated membership tests — in_array is O(n) per call; flip once for O(1).
• Integer overflow in binary search midpoint: (left + right) / 2 — use left + (right - left) / 2.
• Off-by-one errors in binary search boundaries — test with arrays of size 0, 1, 2, and even/odd.

Code Examples

// Linear search in loop — O(n²):
$allowed = ['admin', 'editor', 'viewer']; // Could be 1000 roles
foreach ($users as $user) {
    if (in_array($user->role, $allowed)) { // O(n) per user
        grantAccess($user);
    }
}

// Hash lookup — O(1) per user, O(n) total:
$allowed = array_flip(['admin', 'editor', 'viewer']); // Flip once
foreach ($users as $user) {
    if (isset($allowed[$user->role])) { // O(1)
        grantAccess($user);
    }
}

// Binary search for sorted data:
function binarySearch(array $arr, int $target): int {
    $left = 0; $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2); // Avoids overflow
        if ($arr[$mid] === $target) return $mid;
        $arr[$mid] < $target ? ($left = $mid + 1) : ($right = $mid - 1);
    }
    return -1;
}

References

• ↗ https://en.wikipedia.org/wiki/Binary_search_algorithm

Tags

Related Terms