Searching Algorithms
debt(d5/e3/b3/t5)
Closest to 'specialist tool catches' (d5), phpstan and blackfire profiler can flag in_array() in hot paths or O(n) lookups; binary search bugs on unsorted data are silent though, leaning toward d5-d7.
Closest to 'simple parameterised fix' (e3), quick_fix is replacing in_array() with array_flip()+isset() or swapping to binary search — pattern-level substitution, not architectural.
Closest to 'localised tax' (b3), search choice is usually scoped to specific hot paths or components rather than system-wide; applies_to covers web/cli but each use is localised.
Closest to 'notable trap' (t5), the misconception that binary search is always better and the silent wrong-result trap on unsorted data are classic documented gotchas most devs learn the hard way.
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;
}