Binary search – O(log n) vs O(n) with comparison table

Linear search always works. You go through every element one by one and eventually find what you are looking for. The problem appears with 100,000 elements when you do this in a loop. Binary search solves that problem elegantly – but only if the data is sorted.

Linear search – the baseline

<?php

function linearSearch(array $arr, mixed $target): int
{
    foreach ($arr as $index => $value) {
        if ($value === $target) return $index;
    }
    return -1;
}

Complexity: O(n). With n = 100,000 elements: up to 100,000 comparisons.

Binary search – iterative implementation

<?php

function binarySearch(array $arr, mixed $target): int
{
    $left  = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);

        if ($arr[$mid] === $target) return $mid;

        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return -1;
}

$data = range(1, 100000);
echo binarySearch($data, 99999); // at most 17 comparisons

Complexity: O(log n). n = 100,000 → max 17 comparisons. n = 1,000,000 → only 20.

Binary search on associative arrays

<?php

function binarySearchByKey(array $arr, mixed $target, string $key): int
{
    $left = 0; $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);
        if ($arr[$mid][$key] === $target) return $mid;
        if ($arr[$mid][$key] < $target) $left = $mid + 1;
        else $right = $mid - 1;
    }
    return -1;
}

$products = [
    ['name' => 'Gadget',      'price' => 9.99],
    ['name' => 'Doohickey',   'price' => 14.99],
    ['name' => 'Widget',      'price' => 29.99],
    ['name' => 'Contraption', 'price' => 99.99],
];

$index = binarySearchByKey($products, 29.99, 'price');
echo $products[$index]['name']; // Widget

Complexity comparison

Summary

Binary search is a classic example of how the choice of algorithm matters regardless of the programming language. Database indexes work on a similar principle (B-tree). Understanding this helps you appreciate why a query without an index on a million-row table is slow.