Binary search: boundaries, duplicates and total cost

What you will learn

• Search a sorted integer list and return the first matching index.
• State and maintain a shrinking candidate interval.
• Separate logarithmic search cost from linear input validation.

Theory: remove impossible candidates

Binary search uses order to discard part of a candidate range after each comparison. It requires a sorted structure with a suitable access model. It is not correct to apply it to an arbitrary unsorted list.

Our contract accepts a zero-based PHP list of integers in nondecreasing order, including duplicates and negative values. It returns the lowest index equal to the target, or null. It rejects an invalid type, non-list keys or decreasing pair instead of silently sorting the caller’s input.

This is useful when reasoning about indexed lookups, boundary bugs and interview problems. It is not an instruction to replace a database index with loading every row into PHP. A database must choose an appropriate query/index plan for stored data.

Worked example: leftmost binary search

Required: PHP 8.4+ CLI. Save the whole file as binary_search.php. Use any compatible PHP installation; Laragon/XAMPP are optional.

<?php

declare(strict_types=1);

function firstSortedIndex(array $values, int $target): ?int
{
    if (! array_is_list($values)) {
        throw new InvalidArgumentException('Provide a sorted integer list.');
    }
    foreach ($values as $index => $value) {
        if (! is_int($value) || ($index > 0 && $value < $values[$index - 1])) {
            throw new InvalidArgumentException('Provide a sorted integer list.');
        }
    }

    $low = 0;
    $high = count($values) - 1;
    $found = null;
    while ($low <= $high) {
        $middle = $low + intdiv($high - $low, 2);
        if ($values[$middle] >= $target) {
            if ($values[$middle] === $target) {
                $found = $middle;
            }
            $high = $middle - 1;
        } else {
            $low = $middle + 1;
        }
    }

    return $found;
}

if (realpath($_SERVER['SCRIPT_FILENAME'] ?? '') === __FILE__) {
    foreach ([[[1, 3, 3, 7], 3], [[1, 3, 3, 7], 4], [[], 3]] as [$values, $target]) {
        $index = firstSortedIndex($values, $target);
        echo 'Index: '.($index === null ? 'none' : $index).PHP_EOL;
    }
}

Run and trace a duplicate match

Windows PowerShell:

php --version
php ./binary_search.php

Ubuntu Bash:

php --version
php ./binary_search.php

Index: 1
Index: none
Index: none

Use PHP on PATH; the shared source is identical for both shells. Windows PHP 8.4.26 was executed; Ubuntu execution is not claimed.

For 1,3,3,7 and target 3, the first middle is index 1, so found becomes 1. The algorithm still searches the left side because an earlier equal value might exist. The loop ends when no candidate indices remain. An empty list starts with high=-1, so it never reads an element. The direct-execution guard keeps require-based tests quiet.

Loop invariant and termination

At each iteration, any earlier match not yet ruled out lies in the inclusive interval low..high; found holds the best matching index discovered so far, or null. When the middle value is at least the target, no index to its right can improve the earliest answer. If equal, remember the index, then search left. When the middle value is smaller, no index at or left of middle can match, so search right.

Every iteration removes middle as well as a side. Using middle-1 or middle+1 makes the interval strictly smaller. Reusing middle as a bound can cause an infinite loop in a two-element range. The midpoint formula avoids adding the two bounds directly.

Complexity: count the full function

The search phase makes O(log n) comparisons on a prevalidated sorted list under the stated constant-time indexed-access model. Extra working space is O(1); this version uses no recursive call stack or sliced arrays.

However, this complete safe function scans all input values to check integer types and sorted order. Its total running time is O(n) per call, including validation. Claiming the whole function is O(log n) would be incorrect. If you need many searches, validate a dataset once behind a clear immutable boundary, then search it repeatedly; design and test that boundary separately.

PHP arrays are ordered maps, so their memory representation differs from compact numeric arrays. Big O is a model of growth, not a timing benchmark or a claim about every runtime’s worst-case map access.

Guided lab

1. Trace low, high, middle and found for empty, one-item and two-item lists.
2. Search for the first/last item, a missing gap value, and targets below/above the range.
3. Try 2,2,2 with target 2; expect index 0. Use a strict null check so index 0 is not mistaken for not found.
4. Reject an unsorted pair, a numeric string and an associative outer array. Do not sort them to hide a contract error.
5. Compare repeated calls and verify the input did not change. Write the invariant next to your trace.

Independent exercise

Implement lastSortedIndex() for the last matching index with the same validation rules. For 1,3,3,7 and target 3 return 2; for 2,2,2 return 2; for missing input/target return null. Hint: after equality, remember the index and search right instead of left.

Compare both functions with simple linear reference searches over small sorted fixtures. Include negative integers, all equal values, empty lists and absent targets. Explain the search-phase cost and total validation-inclusive cost separately.

Common mistakes and interview

Mistakes include searching unsorted input, treating index 0 as false/not found, returning an arbitrary duplicate, failing to shrink the interval, copying subarrays every iteration, and forgetting the validation scan in the complexity explanation.

Interview: “Why is this binary search correct?” State the contract, invariant, branch reasoning and termination; then give edge cases and separate total cost from the inner search phase. A familiar algorithm name is not a proof.

English practice and glossary

• Sorted: values follow a defined ordering.
• Candidate interval: indices still needing investigation.
• Invariant: a fact preserved through the loop.
• Leftmost match: the lowest matching index.
• Logarithmic: growth from repeatedly reducing the problem by a factor.
• Precondition: a rule that must hold before an operation.

Say: “The input must be __. I keep __ true. This branch removes __ because __. Including validation, the cost is __.” Record your own trace and a corrected boundary mistake in the private journal.

Recap and next step

Use order and a shrinking interval to justify every discarded candidate. Return the first match deliberately and preserve the caller’s input. Next practise stack/queue and two-pointer invariants, then recursion and trees. Keep full-function costs honest.