MidПрактика11 min

Бинарный поиск

Классический бинарный поиск, поиск на ответ, boundary search

AlgoInterview patterns

Классический бинарный поиск

Поиск элемента в отсортированном массиве за O(log n).

<?php
declare(strict_types=1);

/**
 * @param list<int> $arr
 */
function binarySearch(array $arr, int $target): int
{
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2); // Overflow protection

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

    return -1;
}
## Поиск левой границы (первое вхождение) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $arr
 */
function searchLeft(array $arr, int $target): int
{
    $left = 0;
    $right = count($arr) - 1;
    $result = -1;

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

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

    return $result;
}

// arr = [1, 2, 2, 2, 3, 4], target = 2
// Answer: 1 (first occurrence of 2)
## Поиск правой границы (последнее вхождение) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $arr
 */
function searchRight(array $arr, int $target): int
{
    $left = 0;
    $right = count($arr) - 1;
    $result = -1;

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

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

    return $result;
}
## Бинарный поиск на ответ

Когда прямой поиск невозможен, но можно проверить, подходит ли конкретное значение.

Шаблон: если функция монотонна (чем больше x, тем больше/меньше f(x)), то можно искать x бинарно.

Задача: Koko Eating Bananas

Условие: n кучек бананов, h часов. Какая минимальная скорость k (бананов в час)?

<?php
declare(strict_types=1);

/**
 * @param list<int> $piles
 */
function minEatingSpeed(array $piles, int $h): int
{
    $left = 1;
    $right = max($piles);

    while ($left < $right) {
        $mid = $left + intdiv($right - $left, 2);
        $hours = 0;
        foreach ($piles as $p) {
            $hours += intdiv($p + $mid - 1, $mid); // ceil($p / $mid)
        }

        if ($hours <= $h) {
            $right = $mid;      // Can go slower
        } else {
            $left = $mid + 1;   // Need to go faster
        }
    }

    return $left;
}

// piles = [3, 6, 7, 11], h = 8
// mid=7: hours = 1+1+1+2 = 5 <= 8, right=7
// mid=4: hours = 1+2+2+3 = 8 <= 8, right=4
// mid=2: hours = 2+3+4+6 = 15 > 8, left=3
// mid=3: hours = 1+2+3+4 = 10 > 8, left=4
// left == right == 4. Answer: 4
### Задача: Search in Rotated Sorted Array 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 */
function searchRotated(array $nums, int $target): int
{
    $left = 0;
    $right = count($nums) - 1;

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

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

        // Determine which half is sorted
        if ($nums[$left] <= $nums[$mid]) { // Left half is sorted
            if ($nums[$left] <= $target && $target < $nums[$mid]) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        } else { // Right half is sorted
            if ($nums[$mid] < $target && $target <= $nums[$right]) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
    }

    return -1;
}

// [4, 5, 6, 7, 0, 1, 2], target = 0
// mid=7: left sorted [4,5,6,7], 0 not in [4,7) -> right half
// mid=1: right sorted [0,1,2], 0 in (1,2] no -> left=mid+1
// Recalculate... mid=4(idx), val=0 = target -> return 4
### Задача: Find Minimum in Rotated Array 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 */
function findMin(array $nums): int
{
    $left = 0;
    $right = count($nums) - 1;

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

        if ($nums[$mid] > $nums[$right]) {
            $left = $mid + 1;   // Minimum is on the right
        } else {
            $right = $mid;       // Minimum is on the left (including mid)
        }
    }

    return $nums[$left];
}

// [3, 4, 5, 1, 2]
// mid=5 > right=2 -> left=3 (idx)
// left == right -> nums[3] = 1
### Задача: Square Root (целая часть) 
<?php
declare(strict_types=1);

function mySqrt(int $x): int
{
    if ($x < 2) {
        return $x;
    }

    $left = 1;
    $right = intdiv($x, 2);

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

        if ($square === $x) {
            return $mid;
        } elseif ($square < $x) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return $right; // right = floor(sqrt(x))
}
## Шаблоны бинарного поиска 
<?php
declare(strict_types=1);

// Template 1: Exact search
while ($left <= $right) {
    $mid = $left + intdiv($right - $left, 2);
    if ($arr[$mid] === $target) { return $mid; }
    elseif ($arr[$mid] < $target) { $left = $mid + 1; }
    else { $right = $mid - 1; }
}
return -1;

// Template 2: Left boundary (first true)
while ($left < $right) {
    $mid = $left + intdiv($right - $left, 2);
    if (condition($mid)) {
        $right = $mid;
    } else {
        $left = $mid + 1;
    }
}
return $left;

// Template 3: Right boundary (last true)
while ($left < $right) {
    $mid = $left + intdiv($right - $left + 1, 2); // Round up!
    if (condition($mid)) {
        $left = $mid;
    } else {
        $right = $mid - 1;
    }
}
return $left;
## Типичные ловушки
  1. Бесконечный цикл: while left < right с right = mid работает. Но left = mid без округления вверх зацикливается.
  2. Integer overflow: используй mid = left + (right - left) / 2 вместо (left + right) / 2.
  3. Off-by-one: определи четко, что означают left и right (включительно или нет).

Запомни: Бинарный поиск не только для отсортированных массивов. Если функция монотонна — можно искать на ответе. Три шаблона: точный поиск, левая граница, правая граница. На интервью: если видишь O(n) решение и данные отсортированы — подумай о бинарном поиске для O(log n).

Итоги

  1. Классический: left <= right, O(log n)
  2. Левая/правая граница: left < right, разное направление сужения
  3. Бинарный поиск на ответ: проверяем condition(mid)
  4. Rotated array: определи отсортированную половину
  5. Защита от overflow: mid = left + (right - left) // 2

Проверь себя

В задаче Search in Rotated Sorted Array [4, 5, 6, 7, 0, 1, 2], как определить, какая половина отсортирована?

В массиве [1, 2, 2, 2, 3, 4] при поиске первого вхождения числа 2, что делает алгоритм когда находит target?

Какое условие цикла используется в шаблоне поиска левой границы (first true) в бинарном поиске?

В задаче Koko Eating Bananas (piles = [3, 6, 7, 11], h = 8), какова минимальная скорость поедания бананов?

Почему для вычисления mid используют `$left + intdiv($right - $left, 2)` вместо `intdiv($left + $right, 2)`?

Связанные темы

HashSet: уникальность и поиск

Связанная тема

Дерево поиска BST

Связанная тема

Поиск в глубину DFS

Связанная тема

Backtracking

Связанная тема

Жадные алгоритмы

Связанная тема