Binary search — O(log n) lookups on sorted data

Intermediate5 min read·eng-08-003

interview

Concept

Binary search finds a target in a sorted array in O(log n) time. Each step eliminates half the remaining candidates.

How it works:

Compute mid = (left + right) / 2.
If arr[mid] === target, return mid.
If arr[mid] < target, the target must be in the right half: left = mid + 1.
If arr[mid] > target, the target must be in the left half: right = mid - 1.
Repeat until left > right (not found).

Pre-condition: The array MUST be sorted. Binary search returns undefined behavior on unsorted data.

O(log n) intuition: 1 billion elements → at most 30 steps (log₂ 1,000,000,000 ≈ 30).

Common variants:

Find exact target: Standard binary search.
Find leftmost position of target (first occurrence): When arr[mid] === target, don't return — continue left (right = mid - 1), record the position.
Find rightmost position: When arr[mid] === target, continue right (left = mid + 1), record the position.
Find insertion point: Where would target be inserted to keep array sorted?

PHP built-in: PHP has no built-in binary search. array_search() is O(n). Sort with sort() then use binary search.

Database relevance: B-tree indexes in databases are a generalization of binary search — each node can have many children, and the tree stays balanced. Finding a row by indexed column is O(log n) — this is why indexes make queries fast.

Code Example

php

<?php
// Basic binary search — returns index or -1
function binarySearch(array $sorted, int $target): int
{
    $left  = 0;
    $right = count($sorted) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2); // avoids overflow vs ($left + $right) / 2

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

$arr    = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
$index  = binarySearch($arr, 13); // 6
$notFound = binarySearch($arr, 8); // -1

// Find first occurrence of target (leftmost)
function searchFirst(array $sorted, int $target): int
{
    $left = 0; $right = count($sorted) - 1; $result = -1;
    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);
        if ($sorted[$mid] === $target) { $result = $mid; $right = $mid - 1; } // go left!
        elseif ($sorted[$mid] < $target) $left = $mid + 1;
        else                             $right = $mid - 1;
    }
    return $result;
}

// Find insertion point (where target WOULD go to maintain sort order)
function searchInsertionPoint(array $sorted, int $target): int
{
    $left = 0; $right = count($sorted);
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        if ($sorted[$mid] < $target) $left  = $mid + 1;
        else                          $right = $mid;
    }
    return $left; // left is the insertion index
}

// Search in rotated sorted array (classic interview problem)
// [4, 5, 6, 7, 0, 1, 2] — rotated at index 4
function searchRotated(array $arr, int $target): int
{
    $left = 0; $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);
        if ($arr[$mid] === $target) return $mid;

        if ($arr[$left] <= $arr[$mid]) { // left half is sorted
            if ($arr[$left] <= $target && $target < $arr[$mid]) $right = $mid - 1;
            else                                                  $left  = $mid + 1;
        } else {                          // right half is sorted
            if ($arr[$mid] < $target && $target <= $arr[$right]) $left  = $mid + 1;
            else                                                   $right = $mid - 1;
        }
    }
    return -1;
}

echo searchRotated([4, 5, 6, 7, 0, 1, 2], 0); // 4
echo searchRotated([4, 5, 6, 7, 0, 1, 2], 3); // -1

// Real-world: binary search on sorted DB result
// SELECT id FROM products ORDER BY price ASC;
// Then binary search to find the first product over $50 — O(log n)

PreviousSorting algorithms — bubble, merge, quick sort — PHP usort() internalsAlgorithms in PHP NextRecursion and dynamic programming — memoization patternsAlgorithms in PHP