Linear And Binary Search

Linear search checks items in sequence. Binary search repeatedly halves a sorted search range.

Why This Matters

Binary search is important because it demonstrates how a maintained invariant can change linear work into logarithmic work, but it is only correct when ordering and comparison rules agree.

Working Model

For binary search, maintain a range that may still contain the target, inspect its midpoint, and discard the impossible half. Decide whether the result is any match, first match, insertion point, or range boundary.

Practical Rules

• Use linear search for small or unsorted one-off data.
• Define the sort key and comparator.
• Avoid midpoint arithmetic that can overflow in fixed-width languages.
• Handle duplicates deliberately.
• Prefer database indexes for database-resident search.

Failure Modes

• Applying binary search to unsorted data.
• Sorting for one lookup when sorting costs more than scanning.
• Comparing numeric strings inconsistently.
• Returning an arbitrary duplicate when the caller needs the first.

Verification

• Test empty, one-item, missing, first, last, and duplicate cases.
• Compare against a trusted linear implementation.
• Assert sorted input in development utilities.
• Measure repeated-query workloads.

What You Should Be Able To Do

After this lesson, you should be able to explain linear and binary search, their invariants, and when logarithmic lookup justifies sorted data, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Search Is A Contract About Order

Search code answers a simple question only when the surrounding contract is clear. What counts as a match? Is the input sorted? Which comparison rule defines the order? Should the result be any matching item, the first matching item, the last matching item, or the position where a missing value should be inserted? Linear search and binary search solve different versions of this problem.

Linear search is the default when the data is small, unsorted, or searched only once. It checks items in sequence until it finds a match or reaches the end. Its strength is simplicity. It requires no ordering invariant and can use any predicate that returns true or false. Its cost grows with the number of items inspected.

Binary search is useful when the data is already sorted, or when the cost of sorting can be justified across many searches. It keeps a candidate range that may still contain the target. Each comparison with the midpoint discards the half of the range that cannot contain the answer. The cost grows logarithmically with the number of items, but correctness depends entirely on the sorted-order invariant.

That invariant is the heart of the lesson. Binary search is not just a faster loop. It is a proof that discarded items cannot contain the desired answer. If the list is sorted by case-insensitive name but the search compares case-sensitively, the proof is broken. If numeric strings are sorted lexicographically but searched numerically, the proof is broken. If the data changes while another part of the program assumes the old order, the proof is broken.

Linear Search In PHP

A linear search can be written as a loop over values. The code below finds the first user with a matching email address:

<?php

declare(strict_types=1);

$users = [
    ['id' => 10, 'email' => 'ada@example.test'],
    ['id' => 11, 'email' => 'grace@example.test'],
    ['id' => 12, 'email' => 'linus@example.test'],
];

$found = null;
foreach ($users as $user) {
    if ($user['email'] === 'grace@example.test') {
        $found = $user;
        break;
    }
}

echo $found['id'] . PHP_EOL;

// Prints:
// 11

This is often the right choice for a one-off search through a small in-memory list. It is easy to read, easy to test, and works even if the list has no useful order. It can also express richer predicates, such as active users whose account is not locked and whose subscription expires after today.

The weakness appears when the same search is repeated over a large list. If one request searches the same 10,000 users for 5,000 email addresses, repeated linear scans produce a large amount of avoidable work. A map keyed by normalized email may be the better structure. The right comparison is not binary search versus linear search in isolation; it is one scan, repeated scans, a lookup map, a database index, or a sorted range, depending on where the data lives.

Binary Search Step By Step

Binary search maintains two boundaries around the range that may still contain the target. At each step, it chooses a midpoint and compares the midpoint value with the target. If the midpoint value is too small, the lower half cannot contain the answer. If it is too large, the upper half cannot contain the answer. If it matches, the search has found at least one matching position.

<?php

declare(strict_types=1);

function binarySearch(array $numbers, int $target): int|null
{
    $low = 0;
    $high = count($numbers) - 1;

    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);

        if ($numbers[$mid] === $target) {
            return $mid;
        }

        if ($numbers[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    return null;
}

echo binarySearch([2, 4, 8, 16, 32], 16) . PHP_EOL;
var_export(binarySearch([2, 4, 8, 16, 32], 7));
echo PHP_EOL;

// Prints:
// 3
// NULL

This example returns any exact match. That is not always enough. If duplicates are possible, callers often need the first matching position, the last matching position, or the range of matches. A normal binary search may find a duplicate in the middle and stop too early for those requirements.

First Match, Last Match, And Insertion Points

Search requirements become more interesting when the target may be absent or duplicated. An autocomplete feature may need the first item whose prefix is at least a value. A scheduler may need the insertion point for a new timestamp. A report may need the first and last record for a date.

To find the first matching value, keep searching left after a match and remember the best position found so far. To find the last matching value, keep searching right after a match. To find an insertion point, search for the first value greater than or equal to the target. These variants are often called lower-bound and upper-bound searches.

The important point is that found is not a complete specification. A review should ask what the caller will do with duplicates and missing values. If the caller needs stable pagination or range boundaries, returning an arbitrary duplicate can create inconsistent behavior that appears only with real production data.

Comparator Consistency

Binary search requires the same ordering rule used to sort the data. That sounds obvious until strings, casing, locale, numeric strings, and compound keys enter the program. Sorting users by display name while searching by username is wrong. Sorting strings with one comparison rule and searching with another can be wrong. Sorting records by last_name but searching by created_at is wrong.

PHP code should make the comparator visible. If a sorted list is passed into a helper, the helper's name or documentation should state the expected order. For compound values, prefer a small named comparison function over repeating comparison fragments in different files. That reduces the chance that sorting and searching drift apart.

Numeric strings deserve special care. Values such as '2', '10', and '100' sort differently as strings than as integers. If identifiers are strings, treat them as strings consistently. If quantities are numbers, convert and validate them before sorting and searching. Mixing rules is how a search can pass small tests and fail on realistic data.

When A Database Should Search

If the data already lives in a database, do not pull a large table into PHP just to binary-search it. A database index exists to make lookup and range queries efficient near the data. Let the database search when the authoritative data is there, especially when the query can use an index and return only the needed rows.

PHP search is appropriate after data is already in memory for another reason, for small configuration lists, for local transformations, or for algorithm exercises where the point is the invariant. Application architecture matters more than the name of the algorithm. Searching 100 in-memory values is not the same problem as searching 10 million database rows.

A useful rule is to ask where the sorted order is maintained. If a database index maintains it, query the database. If a PHP array is built and sorted in the request, PHP may search it. If no one maintains the order, binary search is not available until that invariant is created and paid for.

Cost Of Sorting

Binary search is logarithmic after the data is sorted. Sorting itself costs work, commonly more than one linear scan for one lookup. If you sort a list only to answer one membership question, the total cost may be worse than linear search. Sorting pays off when order is already required for another reason or when many searches reuse the same sorted list.

A lookup map can be better than binary search for exact-match repeated lookups. A map does not provide ordered range queries, but it can answer direct key membership naturally. Binary search is stronger when order matters: insertion points, nearest values, prefix ranges, time ranges, and sorted pagination.

This is the decision model: linear search for small or one-off unsorted data; a map or set for repeated exact membership; binary search for repeated or order-sensitive search over sorted in-memory data; a database index when the data is database-resident.

Testing Search Code

Search code needs boundary tests. Empty input should return the documented missing result. A one-item input should succeed and fail correctly. The first and last positions should work. Missing values below the first item, between two items, and above the last item should work. Duplicate values should follow the documented policy. If the function returns an insertion point, test every gap.

A strong technique is to compare a binary-search implementation against a trusted linear implementation over many small generated cases. The linear version is slower but easier to reason about. For each sorted fixture, ask both implementations for the result and confirm that the optimized version matches the simple specification. This is especially useful for first-match, last-match, and insertion-point variants where off-by-one errors are common.

When performance matters, measure repeated-query workloads rather than one isolated call. Include the cost of sorting if the program performs the sort inside the same request. Excluding setup cost can make binary search look better than the actual feature.

After this lesson, you should be able to choose between linear search, binary search, lookup maps, and database indexes; state the ordering invariant required for binary search; define duplicate and missing-value behavior; and verify the implementation with boundary cases that expose incorrect comparisons and off-by-one errors.