---
title: "Бинарный поиск (массив)"
url: https://algopath.pro/ru/patterns/binary-search-array
language: ru
summary: "Посмотрите на середину отсортированного отрезка и выбросьте половину, где ответа быть не может. Повторяйте до одного элемента."
updated: 2026-08-24
---

# Бинарный поиск (массив)

Посмотрите на середину отсортированного отрезка и выбросьте половину, где ответа быть не может. Повторяйте до одного элемента.

## Бинарный поиск (массив): как это работает?

Держите две границы, низ и верх, на отсортированном отрезке. Ответ, если он есть, лежит между ними.

Возьмите средний индекс этого отрезка. Сравните стоящее там значение с искомым.

При совпадении поиск закончен. Верните этот индекс.

Если среднее значение мало, цель лежит правее. Сдвиньте низ за середину.

Если оно велико, сдвиньте верх левее середины. В обоих случаях половина отрезка исчезает.

Цикл кончается, когда низ обогнал верх. Отрезок пуст, значит цели нет.

- `lo=0 hi=5` Ищем 7 в [1, 3, 5, 7, 9, 11]. Кандидатов шесть.
- `mid=2, значение 5` 5 меньше 7. Всё левее выбывает.
- `lo=3 hi=5, mid=4, значение 9` 9 больше 7. Всё правее выбывает.
- `lo=3 hi=3, mid=3, значение 7` Остался один кандидат, и он подходит.
- `возврат 3` Три сравнения на шесть элементов. Удвоение входа добавит одно.

## Бинарный поиск (массив): когда применять?

- отсортированный массив
- найти цель / первое или последнее вхождение
- n до 1e6+ и ожидается O(log n)
- найти границу, где условие меняется
- поиск во вращённом, но почти отсортированном массиве (с подвохом)

## Бинарный поиск (массив): с чем путают?

- **Линейный поиск** - Перебор читает каждый элемент, но порядка не требует. Бинарному поиску порядок нужен, зато он читает log n.
- **Бинарный поиск во вращённом массиве** - Поворот рвёт единый отсортированный кусок. Проверка сначала ищет отсортированную половину.
- **Бинарный поиск по ответу** - Там отрезок это множество возможных ответов, а не массив. Проверку вы пишете сами.
- **Двоичное дерево поиска** - Дерево делит пополам так же, но через указатели. Ещё оно допускает вставки, чего массив не умеет.
- **Два указателя (с концов)** - Там двигаются оба конца, и проверяемая пара меняется. Здесь за шаг двигается одна граница.

## Бинарный поиск (массив): сложность по времени и памяти

n до 1e9 нормально, потому что log2 от 1e9 около 30. Время O(log n), память O(1).

## Бинарный поиск (массив): разбор примера

### Первая и последняя позиция значения

В отсортированном массиве одно значение может повторяться много раз. Верните первый и последний индекс цели.

Если значения нет, верните минус один дважды.

Запустите поиск дважды с разным правилом при совпадении.

Для первого индекса после совпадения двигайте верх влево. Для последнего двигайте низ вправо.

```javascript
function searchRange(nums, target) {
    function bound(findFirst) {
        let lo = 0;
        let hi = nums.length - 1;
        let found = -1;

        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2); // cannot overflow

            if (nums[mid] === target) {
                found = mid;
                // a match is not the end: keep squeezing the chosen side
                if (findFirst) hi = mid - 1;
                else lo = mid + 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return found;
    }

    return [bound(true), bound(false)];
}
```

## Бинарный поиск (массив): частые ошибки

- **Считают mid как lo плюс hi пополам** Такая сумма может выйти за безопасный диапазон. Пишите lo плюс половина разрыва.
- **Двигают границу в mid, а не за него** Отрезок перестаёт сжиматься, и цикл не кончается. Берите mid плюс один или mid минус один.
- **Смешивают два вида цикла** При lo <= hi обе границы входят в отрезок. Смена одной границы без другой ломает инвариант.
- **Ищут в неотсортированных данных** Сравнение считает, что слева от mid всё меньше. Без этого ответ тихо неверен.

## Бинарный поиск (массив): задачи с собеседований

- **Бинарный поиск** Чистая форма на различных отсортированных значениях.
- **Позиция для вставки** Верните место, куда значение встало бы, если его нет.
- **Первая и последняя позиция элемента** Два поиска с противоположным правилом при совпадении.
- **Поиск пика** Сравнение идёт с соседом, а не с целью.
- **Квадратный корень** Отрезок это множество ответов, а не массив.
- **Поиск в двумерной матрице** Считайте всю сетку одним отсортированным списком.
- **Наименьшая буква больше заданной** Верхняя граница, которая заворачивается к началу.

## JavaScript

```javascript
function binarySearch(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
```

## Python

```python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
```

## PHP

```php
function binarySearch(array $arr, $target) {
    $lo = 0; $hi = count($arr) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $lo = $mid + 1;
        else $hi = $mid - 1;
    }
    return -1;
}
```