Бинарный поиск на Python и ещё 7 алгоритмов поиска и сортировки с кодом

Бинарный поиск на Python делит отсортированный список пополам и в миллионе чисел находит элемент за 20 сравнений.

Разбираем итеративный и рекурсивный код, модуль bisect, линейный поиск и шесть сортировок от пузырька до подсчёта.

Каждый пример запущен, а замер показывает, во сколько раз своя сортировка медленнее sorted().

Статью написал:
Ваня Буявец, продюсер, основатель Checkroi
Ваня Буявец
Основатель Checkroi, продюсер, эксперт в выборе онлайн-курсов
Все 3308 статей автора Подписаться на Телеграм-канал
Одобрено экспертом:
Наташа Буявец, основатель Checkroi, эксперт по онлайн-курсам
Наташа Буявец
Основательница Checkroi, продюсер Youtube-каналов, эксперт по онлайн-курсам
Все 3962 экспертных мнения Подписаться на Телеграм-канал
Обложка: Бинарный поиск на Python и ещё 7 алгоритмов поиска и сортировки с кодом

Бинарный поиск на Python находит элемент в отсортированном списке, каждый раз деля диапазон пополам: смотрит на середину, отбрасывает половину, где искомого быть не может, и повторяет. В списке из миллиона чисел хватает 20 сравнений. Готовая реализация лежит в стандартной библиотеке, в модуле bisect, но написать функцию самому полезно хотя бы раз: её часто дают на собеседованиях.

В статье бинарный и линейный поиск, шесть сортировок от пузырька до подсчёта, таблица сложности и замер скорости каждой реализации против встроенной sorted(). Сама sorted() и метод списка разобраны отдельно, в статье про метод sort() в Python.

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

Рой открывает толстый справочник ровно посередине

Алгоритм хранит две границы, low и high. На каждом шаге он берёт средний индекс и сравнивает элемент с искомым:

  1. элемент в середине равен искомому, значит индекс найден;
  2. элемент меньше искомого, значит искать надо правее, и левая граница переезжает на mid + 1;
  3. элемент больше, значит искать надо левее, и правая граница переезжает на mid - 1;
  4. если 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). Вставка сдвигает все элементы правее новой позиции.

Канал основателя Checkroi Вани Буявца3 800 человек читают мой Телеграм-канал про нейросетиСобрал промпты для Claude Code и ChatGPT, разборы ИИ-инструментов и лайфхаки по продвижению бизнеса в одном местеПрисоединиться

Линейный поиск и когда он выгоднее

Линейный поиск проверяет элементы по очереди, пока не найдёт нужный. Сортировка ему не нужна, и в этом его главный плюс:

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 тысяч. Ниже эта разница видна в миллисекундах.

CheckroiCheckroiПодборка курсов по Python574 курса • 53 школыСравните цены, школы, программу и найдите выгодные предложения по обучениюСравнить→

Простые сортировки: пузырьком, выбором, вставками

Цветные бруски разной высоты выстроены по росту

У трёх алгоритмов квадратичная сложность, в рабочем коде их не применяют. Зато на них учатся думать о циклах и перестановках, и их спрашивают на собеседованиях. Все функции работают с копией списка 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.

Ваня БуявецКанал основателя Checkroi Вани БуявцаЗабирайте промпты и обучение по нейросетям в моём Телеграм-каналеБольше 3 800 человек уже применяют Claude Code, ChatGPT и другие нейросети в работе, учёбе, бизнесе и жизниПерейти в канал

Сортировка подсчётом для целых чисел

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. Список не отсортирован. Функция вернёт −1 для числа, которое в списке есть. Решение: отсортировать один раз через sorted() и дальше искать сколько угодно раз.
  2. Бесконечный цикл. Если написать low = mid вместо low = mid + 1, на двух соседних элементах середина перестаёт двигаться. Границы всегда сдвигаются за середину.
  3. Условие low < high вместо low <= high. Цикл заканчивается на шаг раньше, последний оставшийся элемент не проверяется. В списке [1, 2] такая функция не найдёт двойку.
  4. Ожидание первого вхождения. Самописная функция при повторах вернёт любой из одинаковых элементов. Для первого берите bisect_left, для последнего bisect_right(items, x) - 1 с проверкой, что элемент совпал.
  5. Срезы в рекурсии. Каждый items[mid:] копирует данные, и поиск за O(log n) превращается в O(n).
  6. Формула середины из Java. В Java и C++ середину считают как low + (high - low) // 2, чтобы сумма индексов не переполнила тип. Целые числа в Python не переполняются, так что простое (low + high) // 2 безопасно, хотя и вторая формула ничего не ломает.

Где освоить Python и алгоритмы системно

Бинарный поиск и сортировки открывают тему алгоритмов, дальше идут графы, деревья, хеш-таблицы и динамическое программирование. Тренироваться удобно на LeetCode, где задачи разложены по темам и уровням сложности.

Если нужна программа с ревью кода и наставником, ниже курсы по Python из нашего каталога. Путь от первых скриптов до работы разработчиком мы описали отдельно, в статье как стать Python-разработчиком.

КурсШколаСтоимость со скидкойВ рассрочкуДлитель­ностьОбзор курса от Checkroi
Профессия «Python-разработчик»
Перейти на сайт курса
SkillboxSkillbox157 335 ₽5987 ₽/мес.10 месяцевОбзор курса
Fullstack-разработчик на Python
Перейти на сайт курса
НетологияНетология137 000 ₽7125 ₽/мес.21 месяцОбзор курса
ДО Профессия Python-разработчик
Перейти на сайт курса
GeekBrainsGeekBrains149 001 ₽3167 ₽/мес.10 месяцевОбзор курса
Автоматизированное тестирование на Python
Перейти на сайт курса
SkillboxSkillbox118 754 ₽4108 ₽/мес.9 месяцевОбзор курса
Профессия Python-разработчик
Перейти на сайт курса
SkillFactorySkillFactory140 040 ₽3890 ₽/мес.10 месяцевОбзор курса

Больше программ — в полном каталоге курсов по Python

Часто задаваемые вопросы

Что такое бинарный поиск простыми словами?

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

Какая сложность у бинарного поиска?

O(log n): число шагов растёт как двоичный логарифм длины списка. Для тысячи элементов нужно не больше 10 сравнений, для миллиона 20, для миллиарда 30.

Чем бинарный поиск отличается от линейного?

Линейный поиск перебирает элементы по очереди и работает на любом списке, но за O(n). Бинарный работает за O(log n), зато только на отсортированных данных. В нашем замере на миллионе чисел bisect_left() нашёл последний элемент примерно в 45 тысяч раз быстрее, чем list.index().

Есть ли в Python готовый бинарный поиск?

Да, модуль bisect из стандартной библиотеки. Функция bisect_left() возвращает позицию, куда вставить элемент, чтобы список остался отсортированным, а с Python 3.10 у неё есть параметр key для поиска по полю записи.

Какой алгоритм сортировки использует Python?

Встроенные sorted() и list.sort() используют Timsort. По руководству по сортировке на python.org эта сортировка устойчива: элементы с одинаковым ключом сохраняют исходный порядок.

Какие сортировки учить к собеседованию?

Чаще всего просят написать бинарный поиск, сортировку слиянием и быструю сортировку и объяснить их сложность. Пузырёк, выбор и вставки стоит понимать, чтобы сравнить их с алгоритмами за O(n log n). Задачи по темам удобно решать на LeetCode.

Читайте Checkroi первым в Google
Добавьте Checkroi в избранные источники — и наши разборы курсов и обзоры школ будут показываться выше в вашей выдаче Google.
Оставить комментарий
0 комментариев
Форма комментария

Оставьте комментарий

Напишите, что думаете. Нам важно ваше мнение!