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

Поиск последнего элемента, меньшего x, в отсортированном массиве

🐍 Python

n = int(input())
A = list(map(int, input().split()))
x = int(input())

l, r = 0, n

while l < r - 1:
    m = (l + r) // 2
    if A[m] < x:
        l = m
    else:
        r = m

print(l)

⚙️ C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
    
    cin >> x;
    
    int l = 0, r = n, m;
    
    while (l < r - 1) {
        m = (l + r) / 2;
        if (A[m] < x)
            l = m;
        else
            r = m;
    }
    
    cout << l << endl;
    
    return 0;
}

Python (встроенная функция)

import bisect
index = bisect.bisect_left(A, x)

C++ (встроенная функция)

#include <algorithm>
int index = lower_bound(arr.begin(), arr.end(), x) - arr.begin();

Как работает бинарный поиск?

Этот алгоритм реализует правый бинарный поиск (или бинарный поиск по правой границе). Его цель — найти индекс последнего элемента в отсортированном массиве, который строго меньше заданного значения x.

Основная идея

Алгоритм поддерживает два указателя — l (левый) и r (правый). В любой момент времени выполняется важный инвариант:

Все элементы с индексами ≤ l меньше x
Все элементы с индексами ≥ r больше или равны x

Изначально l = 0, r = n. Это значит, что мы ничего не знаем об элементах (инвариант выполняется тривиально, так как отрезки пусты).

Шаги работы

Проверка условия продолжения: while l < r - 1 — цикл продолжается, пока между l и r есть хотя бы один элемент. Если r = l + 1, значит между указателями нет элементов, и поиск завершён.
Вычисление середины: m = (l + r) // 2 — берётся индекс элемента примерно посередине между l и r.
Проверка элемента A[m]:
- Если A[m] < x — этот элемент подходит (меньше x). Сдвигаем левую границу: l = m. Теперь все элементы до m включительно гарантированно меньше x.
- Если A[m] >= x — элемент не подходит (он больше или равен x). Сдвигаем правую границу: r = m. Теперь все элементы с m и правее гарантированно не меньше x.
Повторение — процесс продолжается, пока интервал не сузится до двух соседних индексов.

Завершение алгоритма

Когда цикл заканчивается, l и r становятся соседними индексами (r = l + 1). При этом:

l — это индекс последнего элемента, который гарантированно меньше x
r — это индекс первого элемента, который гарантированно больше или равен x

Временная сложность: O(log n), где n — размер массива.

Пример работы

Для массива A = [1, 3, 5, 7, 9, 11, 13] и x = 10:

Начало: l=0, r=7
m=3 → A[3]=7 < 10 → l=3
m=5 → A[5]=11 >= 10 → r=5
m=4 → A[4]=9 < 10 → l=4
Цикл завершён (l=4, r=5)

Результат: l = 4 (элемент 9 — последний меньший 10)

Важные замечания

Массив должен быть отсортирован по неубыванию
Если все элементы меньше x, то l будет равен n-1
Если все элементы больше или равны x, то l останется 0 (но проверять A[0] < x нужно отдельно)
Алгоритм работает за O(log n) операций
Этот алгоритм часто используется как составная часть более сложных операций: поиск места вставки, нахождение количества элементов меньше x, реализация upper_bound и т.д.

Попробовать бинарный поиск онлайн

Введите отсортированный массив и число x:

Массив (числа через пробел): Число x:

Результат появится здесь...