Binary Search

# Binary Search

Zerethon Official Sample `binary-search`, version 1.4.0, PHP 8.4.

- `binary_search.php` — the algorithm (`binary_search`, and `binary_search_steps` to trace it)
- `main.php` — entry file: searches a few values and prints the steps
- `test_binary_search.php` — checks; set it as the entry file to run them

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/binary-search-visualizer

<?php

// Binary search over a sorted array (Zerethon Official Sample: binary-search 1.4.0).

declare(strict_types=1);

/** Return the index of $target in $a (sorted ascending), or -1 if it is absent. */
function binary_search(array $a, int $target): int
{
    $lo = 0;
    $hi = count($a) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($a[$mid] === $target) {
            return $mid;
        }
        if ($a[$mid] < $target) {
            $lo = $mid + 1;
        } else {
            $hi = $mid - 1;
        }
    }

    return -1;
}

/** Every comparison binary_search makes, as [lo, mid, hi]. */
function binary_search_steps(array $a, int $target): array
{
    $steps = [];
    $lo = 0;
    $hi = count($a) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        $steps[] = [$lo, $mid, $hi];
        if ($a[$mid] === $target) {
            break;
        }
        if ($a[$mid] < $target) {
            $lo = $mid + 1;
        } else {
            $hi = $mid - 1;
        }
    }

    return $steps;
}

<?php

declare(strict_types=1);

require __DIR__.'/binary_search.php';

$numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
echo 'Sorted list: ['.implode(', ', $numbers)."]\n\n";

foreach ([23, 2, 91, 7] as $target) {
    $index = binary_search($numbers, $target);
    $result = $index !== -1 ? "found at index {$index}" : 'not found';
    printf("search %2d: %s\n", $target, $result);
}

echo "\nSteps for 23 (lo, mid, hi):\n";
foreach (binary_search_steps($numbers, 23) as [$lo, $mid, $hi]) {
    echo "  lo={$lo} mid={$mid} hi={$hi} -> a[mid]={$numbers[$mid]}\n";
}

<?php

// Checks for binary_search. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.

declare(strict_types=1);

require __DIR__.'/binary_search.php';

$range = range(0, 998, 2);
$cases = [
    [[], 1, -1],
    [[4], 4, 0],
    [[4], 5, -1],
    [[1, 3, 5, 7, 9], 1, 0],
    [[1, 3, 5, 7, 9], 9, 4],
    [[1, 3, 5, 7, 9], 6, -1],
    [$range, 998, 499],
];

foreach ($cases as [$a, $target, $expected]) {
    $actual = binary_search($a, $target);
    if ($actual !== $expected) {
        fwrite(STDERR, sprintf("binary_search(length %d, %d): expected %d, got %d\n", count($a), $target, $expected, $actual));
        exit(1);
    }
}

echo 'All '.count($cases)." checks passed.\n";