Бинарный поиск на Python находит элемент в отсортированном списке, каждый раз деля диапазон пополам: смотрит на середину, отбрасывает половину, где искомого быть не может, и повторяет. В списке из миллиона чисел хватает 20 сравнений. Готовая реализация лежит в стандартной библиотеке, в модуле bisect, но написать функцию самому полезно хотя бы раз: её часто дают на собеседованиях.
В статье бинарный и линейный поиск, шесть сортировок от пузырька до подсчёта, таблица сложности и замер скорости каждой реализации против встроенной sorted(). Сама sorted() и метод списка разобраны отдельно, в статье про метод sort() в Python.
SkillboxПрофессия «Python-разработчик»157 335 ₽10 месяцев
НетологияFullstack-разработчик на Python137 000 ₽21 месяц
GeekBrainsДО Профессия Python-разработчик149 001 ₽10 месяцев
SkillFactoryПрофессия Python-разработчик140 040 ₽10 месяцев
Академия СинергияPython-разработчик + ИИ77 900 ₽6 месяцев
ЭдюсонPython-разработчик89 919 ₽9 месяцев
Как работает бинарный поиск

Алгоритм хранит две границы, low и high. На каждом шаге он берёт средний индекс и сравнивает элемент с искомым:
- элемент в середине равен искомому, значит индекс найден;
- элемент меньше искомого, значит искать надо правее, и левая граница переезжает на
mid + 1; - элемент больше, значит искать надо левее, и правая граница переезжает на
mid - 1; - если
lowобогналhigh, диапазон пуст и элемента в списке нет.
Каждый шаг вдвое сокращает диапазон, поэтому число шагов растёт как двоичный логарифм длины списка. Для тысячи элементов нужно не больше 10 сравнений, для миллиона 20, для миллиарда 30.
Главное условие одно: список должен быть отсортирован. На неотсортированных данных функция отработает без ошибки и вернёт неверный ответ, поэтому порядок проверяют до поиска.
Тот же принцип работает и вне программирования: так ищут слово в бумажном словаре или страницу в толстой книге. Чем список устроен в памяти и чем он отличается от массива в других языках, рассказали в статье про массивы.
Бинарный поиск на Python: итеративная версия
На собеседованиях и в учебниках чаще всего пишут цикл while. Функция ниже возвращает индекс и число шагов, чтобы было видно, сколько сравнений ушло на поиск:
def binary_search(items, target):
low, high = 0, len(items) - 1
steps = 0
while low <= high:
steps += 1
mid = (low + high) // 2
if items[mid] == target:
return mid, steps
if items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1, steps
prices = [120, 340, 560, 780, 990, 1250, 1490, 1800, 2100, 2500]
print(binary_search(prices, 1490))
print(binary_search(prices, 1000))
numbers = list(range(1_000_000))
print(binary_search(numbers, 999_999))
Вывод:
(6, 4)
(-1, 3)
(999999, 20)
Цену 1 490 функция нашла за 4 шага, отсутствие 1 000 подтвердила за 3. Последнее число в списке из миллиона элементов нашлось за 20 шагов.
Средний индекс считается через //, чтобы он остался целым числом. Почему с обычным слешем Python выдаст TypeError, объяснили в статье про деление в Python, а сам цикл подробно разобран в материале про циклы for и while.
Рекурсивная версия
Ту же логику можно записать через вызов функции из самой себя. Границы передаются аргументами:
def binary_search_rec(items, target, low=0, high=None):
if high is None:
high = len(items) - 1
if low > high:
return -1
mid = (low + high) // 2
if items[mid] == target:
return mid
if items[mid] < target:
return binary_search_rec(items, target, mid + 1, high)
return binary_search_rec(items, target, low, mid - 1)
prices = [120, 340, 560, 780, 990, 1250, 1490, 1800, 2100, 2500]
print(binary_search_rec(prices, 780))
print(binary_search_rec(prices, 5))
Вывод:
3
-1
Каждый рекурсивный вызов занимает кадр стека. Для бинарного поиска это не опасно: глубина равна числу шагов, около 20 для миллиона элементов. Лимит по умолчанию в CPython 1 000 вызовов, текущее значение возвращает sys.getrecursionlimit(). Как устроены такие функции и где у них предел, рассказали в статье о рекурсии в Python.
В рекурсивной версии часто передают срез items[mid + 1:] вместо границ. Срез копирует половину списка на каждом шаге, поиск теряет скорость, а найденный индекс приходится пересчитывать относительно исходного списка.
Модуль bisect
В стандартной библиотеке бинарный поиск уже есть. В документации модуля bisect функция bisect_left() описана как поиск точки вставки, при которой список остаётся отсортированным. Есть ли элемент в списке, она не проверяет, поэтому нужна короткая обёртка:
from bisect import bisect_left, bisect_right, insort
def index_of(items, target):
i = bisect_left(items, target)
if i < len(items) and items[i] == target:
return i
return -1
grades = [2, 3, 3, 3, 4, 5, 5]
print(index_of(grades, 3))
print(index_of(grades, 1))
print(bisect_left(grades, 3), bisect_right(grades, 3))
print(bisect_right(grades, 3) - bisect_left(grades, 3))
insort(grades, 4)
print(grades)
Вывод:
1
-1
1 4
3
[2, 3, 3, 3, 4, 4, 5, 5]
Что здесь произошло:
index_of(grades, 3)вернул 1:bisect_leftвстаёт перед всеми одинаковыми значениями, то есть даёт первое вхождение;bisect_leftиbisect_rightвместе дают границы блока одинаковых элементов, их разница показывает, сколько раз число встречается: три тройки;insort()вставил четвёрку на её место без пересортировки всего списка.
Самописная функция из первого примера на том же списке [2, 3, 3, 3, 4, 5, 5] вернёт индекс 3. Это тройка, но не первая. Когда важна позиция первого вхождения, удобнее bisect_left.
С Python 3.10 у функций модуля есть параметр key, так что искать можно по полю записи, например по цене в списке кортежей. Про insort() в той же документации есть оговорка: быстрый поиск за O(log n) перекрывается медленной вставкой за O(n). Вставка сдвигает все элементы правее новой позиции.
Линейный поиск и когда он выгоднее
Линейный поиск проверяет элементы по очереди, пока не найдёт нужный. Сортировка ему не нужна, и в этом его главный плюс:
def linear_search(items, target):
for i, value in enumerate(items):
if value == target:
return i
return -1
cities = ["Казань", "Пермь", "Омск", "Тула", "Омск"]
print(linear_search(cities, "Омск"))
print(linear_search(cities, "Сочи"))
print("Тула" in cities, cities.index("Тула"))
Вывод:
2
-1
True 3
Функция вернула 2, то есть первый «Омск», хотя в списке их два. Индекс и значение одновременно даёт функция enumerate(). Встроенные оператор in и метод index() тоже перебирают элементы, только цикл у них выполняется внутри интерпретатора и идёт быстрее.
Перебор выгоднее бинарного поиска в четырёх случаях:
- список не отсортирован, а искать нужно один-два раза: сортировка обойдётся дороже самого перебора;
- элементов мало, до нескольких десятков;
- данные приходят потоком, и цикл всё равно проходит по ним целиком;
- ищете по условию: первое отрицательное число, первую строку с ошибкой в логе.
На больших списках разницу видно по цифрам. Вот замер поиска последнего числа в списке из миллиона элементов:
import timeit
from bisect import bisect_left
numbers = list(range(1_000_000))
target = 999_999
linear = timeit.timeit(lambda: numbers.index(target), number=100) / 100
binary = timeit.timeit(lambda: bisect_left(numbers, target), number=100) / 100
print(f"index(): {linear * 1000:.3f} мс")
print(f"bisect_left(): {binary * 1000:.5f} мс")
Вывод:
index(): 5.425 мс
bisect_left(): 0.00012 мс
Метод index() потратил около 5,4 миллисекунды, bisect_left() около 0,12 микросекунды, примерно в 45 тысяч раз быстрее. Замер сделан в ноябре 2026 года на Python 3.14 и Apple M4 Pro, на другом компьютере абсолютные числа будут другими.
Если искать приходится часто, а порядок не нужен, есть вариант быстрее обоих: множество или словарь, где проверка наличия в среднем не зависит от размера.
Сложность алгоритмов поиска и сортировки
Сводка по всем восьми алгоритмам статьи и встроенной сортировке. Здесь n обозначает длину списка, а k разброс значений, то есть максимум минус минимум:
| Алгоритм | Лучший случай | Средний | Худший | Доп. память | Устойчивость |
|---|---|---|---|---|---|
| Линейный поиск | O(1) | O(n) | O(n) | O(1) | |
| Бинарный поиск | O(1) | O(log n) | O(log n) | O(1) в цикле | |
| Пузырьком | O(n) с флагом | O(n²) | O(n²) | O(1) | да |
| Выбором | O(n²) | O(n²) | O(n²) | O(1) | нет |
| Вставками | O(n) | O(n²) | O(n²) | O(1) | да |
| Слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | да |
| Быстрая | O(n log n) | O(n log n) | O(n²) | O(log n) на месте | нет на месте |
| Подсчётом | O(n + k) | O(n + k) | O(n + k) | O(k) | |
| sorted() и list.sort() | O(n) | O(n log n) | O(n log n) | O(n) | да |
Устойчивая сортировка не меняет порядок равных элементов. Если отсортировать заказы по сумме, заказы с одинаковой суммой останутся в той последовательности, в какой были. Встроенная сортировка, по руководству по сортировке на python.org, устойчива всегда, поэтому сложную сортировку можно делать в несколько проходов, по одному ключу за раз.
Оценки O(n²) и O(n log n) кажутся абстрактными, пока не посчитаешь. Для 10 000 элементов n² даёт 100 миллионов операций, а n log n около 130 тысяч. Ниже эта разница видна в миллисекундах.
Простые сортировки: пузырьком, выбором, вставками

У трёх алгоритмов квадратичная сложность, в рабочем коде их не применяют. Зато на них учатся думать о циклах и перестановках, и их спрашивают на собеседованиях. Все функции работают с копией списка items[:] и исходный не меняют.
Сортировка пузырьком
def bubble_sort(items):
items = items[:]
n = len(items)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if not swapped:
break
return items
Соседние элементы сравниваются попарно, и больший «всплывает» в конец, как пузырёк. После каждого прохода последний элемент встаёт на место, поэтому внутренний цикл с каждым разом короче на один шаг.
Флаг swapped останавливает сортировку, если за проход не случилось ни одного обмена. Без него пузырёк делает все проходы даже по уже отсортированному списку.
Сортировка выбором
def selection_sort(items):
items = items[:]
n = len(items)
for i in range(n - 1):
min_i = i
for j in range(i + 1, n):
if items[j] < items[min_i]:
min_i = j
items[i], items[min_i] = items[min_i], items[i]
return items
На каждом шаге алгоритм ищет минимум в неотсортированной части и ставит его в начало. Обменов мало, не больше n − 1. Сравнений же всегда около n²/2, даже на готовом списке, поэтому у выбора нет «лучшего случая».
Сортировка вставками
def insertion_sort(items):
items = items[:]
for i in range(1, len(items)):
current = items[i]
j = i - 1
while j >= 0 and items[j] > current:
items[j + 1] = items[j]
j -= 1
items[j + 1] = current
return items
Алгоритм берёт очередной элемент и сдвигает его влево, пока слева не окажется число меньше или равное. Так раскладывают карты в руке.
На почти отсортированных данных вставки работают почти за линейное время. Встроенная сортировка тоже выигрывает на частично упорядоченных списках: по тому же руководству, Timsort использует порядок, который уже есть в данных.
Сортировка слиянием и быстрая сортировка
Оба алгоритма делят задачу на части и решают их рекурсивно. В среднем они работают за O(n log n), и на больших списках это разница в десятки и сотни раз.
Сортировка слиянием
def merge_sort(items):
if len(items) <= 1:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Список режется пополам, пока не останутся куски по одному элементу, а потом куски сливаются попарно в отсортированном порядке. Результат собирается в новый список через append() и extend(). Сложность O(n log n) в любом случае, но под результат нужна дополнительная память.
Знак <= при сравнении делает сортировку устойчивой: из двух равных элементов первым уходит тот, что стоял левее.
Быстрая сортировка
def quick_sort(items):
if len(items) <= 1:
return items[:]
pivot = items[len(items) // 2]
less = [x for x in items if x < pivot]
equal = [x for x in items if x == pivot]
greater = [x for x in items if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
Алгоритм выбирает опорный элемент, здесь средний, раскладывает остальные на три списка (меньше, равно, больше) и рекурсивно сортирует крайние. Версия на списковых включениях короткая, но создаёт новые списки на каждом уровне. Классическая быстрая сортировка переставляет элементы на месте и экономит память.
В худшем случае опорный элемент раз за разом оказывается минимумом или максимумом. Тогда сложность вырастает до O(n²), а глубина рекурсии до n, и на списке длиннее тысячи элементов Python упрётся в лимит рекурсии. Средний элемент как опора спасает на уже отсортированных данных, а на произвольных опору часто выбирают случайно, через choice() из модуля random.
Сортировка подсчётом для целых чисел
def counting_sort(items):
if not items:
return []
low, high = min(items), max(items)
counts = [0] * (high - low + 1)
for x in items:
counts[x - low] += 1
result = []
for offset, count in enumerate(counts):
result.extend([offset + low] * count)
return result
Этот алгоритм вообще не сравнивает элементы. Он считает, сколько раз встречается каждое значение, и выписывает значения по порядку. Сложность O(n + k), где k обозначает разброс значений.
Подходит для целых чисел в узком диапазоне: оценки от 1 до 5, возраст, баллы ЕГЭ от 0 до 100. Если в списке десять чисел от нуля до миллиарда, массив счётчиков займёт миллиард ячеек, и подсчёт проиграет любой другой сортировке.
Проверка всех шести функций на одном списке. Блок запускается, если положить функции в файл sorts.py:
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10, 3]
for f in (bubble_sort, selection_sort, insertion_sort,
merge_sort, quick_sort, counting_sort):
print(f"{f.__name__:15} {f(data)}")
print(f"{'sorted':15} {sorted(data)}")
Вывод:
bubble_sort [3, 3, 9, 10, 27, 38, 43, 82]
selection_sort [3, 3, 9, 10, 27, 38, 43, 82]
insertion_sort [3, 3, 9, 10, 27, 38, 43, 82]
merge_sort [3, 3, 9, 10, 27, 38, 43, 82]
quick_sort [3, 3, 9, 10, 27, 38, 43, 82]
counting_sort [3, 3, 9, 10, 27, 38, 43, 82]
sorted [3, 3, 9, 10, 27, 38, 43, 82]
Замер: самописные сортировки против sorted()
Каждую функцию прогнали на списке из 5 000 случайных чисел от 0 до 10 000 через модуль timeit и взяли лучший из трёх запусков. Скрипт лежит рядом с sorts.py:
import random
import timeit
from sorts import (bubble_sort, selection_sort, insertion_sort,
merge_sort, quick_sort, counting_sort)
random.seed(42)
data = [random.randint(0, 10_000) for _ in range(5_000)]
for f in (bubble_sort, selection_sort, insertion_sort,
merge_sort, quick_sort, counting_sort, sorted):
t = min(timeit.repeat(lambda: f(data), number=1, repeat=3))
print(f"{f.__name__:15} {t * 1000:9.1f} мс")
Вывод:
bubble_sort 380.4 мс
selection_sort 159.3 мс
insertion_sort 141.6 мс
merge_sort 3.6 мс
quick_sort 2.7 мс
counting_sort 0.8 мс
sorted 0.2 мс
Что видно по цифрам:
- пузырёк медленнее
sorted()примерно в 1 900 раз, выбор и вставки быстрее пузырька, но тоже тратят сотни миллисекунд; - слияние и быстрая сортировка на чистом Python уложились в 3–4 мс, это в 40–140 раз быстрее квадратичных алгоритмов;
- подсчёт обогнал все самописные варианты, потому что значения лежат в узком диапазоне;
sorted()быстрее всех: она написана на C и использует Timsort.
На уже отсортированном списке из 5 000 чисел картина другая: пузырёк с флагом и вставки укладываются в 0,1–0,2 мс, потому что делают один проход и почти ничего не двигают.
В рабочем коде сортируйте через sorted() или list.sort(), а ищите через bisect, множество или словарь. Свои реализации нужны для собеседований, олимпиад и для понимания, почему одни решения выдерживают рост данных, а другие нет. Потренироваться на задачах можно с подборкой из 30 задач по Python.
Частые ошибки в бинарном поиске

- Список не отсортирован. Функция вернёт −1 для числа, которое в списке есть. Решение: отсортировать один раз через
sorted()и дальше искать сколько угодно раз. - Бесконечный цикл. Если написать
low = midвместоlow = mid + 1, на двух соседних элементах середина перестаёт двигаться. Границы всегда сдвигаются за середину. - Условие
low < highвместоlow <= high. Цикл заканчивается на шаг раньше, последний оставшийся элемент не проверяется. В списке[1, 2]такая функция не найдёт двойку. - Ожидание первого вхождения. Самописная функция при повторах вернёт любой из одинаковых элементов. Для первого берите
bisect_left, для последнегоbisect_right(items, x) - 1с проверкой, что элемент совпал. - Срезы в рекурсии. Каждый
items[mid:]копирует данные, и поиск за O(log n) превращается в O(n). - Формула середины из Java. В Java и C++ середину считают как
low + (high - low) // 2, чтобы сумма индексов не переполнила тип. Целые числа в Python не переполняются, так что простое(low + high) // 2безопасно, хотя и вторая формула ничего не ломает.
Где освоить Python и алгоритмы системно
Бинарный поиск и сортировки открывают тему алгоритмов, дальше идут графы, деревья, хеш-таблицы и динамическое программирование. Тренироваться удобно на LeetCode, где задачи разложены по темам и уровням сложности.
Если нужна программа с ревью кода и наставником, ниже курсы по Python из нашего каталога. Путь от первых скриптов до работы разработчиком мы описали отдельно, в статье как стать Python-разработчиком.
| Курс | Школа | Стоимость со скидкой | В рассрочку | Длительность | Обзор курса от Checkroi |
|---|---|---|---|---|---|
| Профессия «Python-разработчик» Перейти на сайт курса | 157 335 ₽ | 5987 ₽/мес. | 10 месяцев | Обзор курса | |
| Fullstack-разработчик на Python Перейти на сайт курса | 137 000 ₽ | 7125 ₽/мес. | 21 месяц | Обзор курса | |
| ДО Профессия Python-разработчик Перейти на сайт курса | 149 001 ₽ | 3167 ₽/мес. | 10 месяцев | Обзор курса | |
| Автоматизированное тестирование на Python Перейти на сайт курса | 118 754 ₽ | 4108 ₽/мес. | 9 месяцев | Обзор курса | |
| Профессия Python-разработчик Перейти на сайт курса | 140 040 ₽ | 3890 ₽/мес. | 10 месяцев | Обзор курса |
Больше программ — в полном каталоге курсов по Python




