Перейти на PRO

Как найти значение в отсортированном списке в Python?

Тип вопроса: Алгоритмы Вероятность: 10% Категория: Python Разработчик

Ответ

Для поиска значения в отсортированном списке в Python существуют различные подходы, отличающиеся по эффективности:

  1. Бинарный поиск (модуль bisect) Это наиболее эффективный способ для отсортированных данных, так как он использует алгоритм бинарного поиска с логарифмической сложностью O(log n). Он работает, постоянно деля область поиска пополам, что значительно быстрее линейного поиска для больших списков. Модуль bisect предоставляет функции для работы с отсортированными списками:

    • bisect_left(a, x): Возвращает индекс, куда x можно вставить в a так, чтобы порядок остался отсортированным. Если x уже есть, возвращает индекс первого вхождения.
    • bisect_right(a, x): Аналогично, но возвращает индекс после всех существующих вхождений x.
    import bisect

sorted_list = [10, 20, 30, 40, 50, 60, 70, 80, 90]
value_to_find = 50
value_not_found = 55

# Поиск существующего значения
index = bisect.bisect_left(sorted_list, value_to_find)
if index < len(sorted_list) and sorted_list[index] == value_to_find:
    print(f"Значение {value_to_find} найдено по индексу: {index}")
else:
    print(f"Значение {value_to_find} не найдено.")

# Поиск несуществующего значения
index_nf = bisect.bisect_left(sorted_list, value_not_found)
if index_nf < len(sorted_list) and sorted_list[index_nf] == value_not_found:
    print(f"Значение {value_not_found} найдено по индексу: {index_nf}")
else:
    print(f"Значение {value_not_found} не найдено.")

  2. Оператор in Простой и идиоматичный способ проверки наличия элемента. Однако, для списков он выполняет линейный поиск (проверяет каждый элемент по порядку) со сложностью O(n), даже если список отсортирован. Он не использует преимущество отсортированности данных.

    sorted_list = [10, 20, 30, 40, 50]
value_to_find = 30

if value_to_find in sorted_list:
    print(f"Значение {value_to_find} присутствует в списке.")
else:
    print(f"Значение {value_to_find} отсутствует в списке.")

  3. Метод list.index() Этот метод возвращает индекс первого вхождения значения. Как и оператор in, он выполняет линейный поиск со сложностью O(n) и не использует свойство отсортированности списка. Если элемент не найден, генерирует ValueError.

    sorted_list = [10, 20, 30, 40, 50]
value_to_find = 40
value_not_found = 100

try:
    index = sorted_list.index(value_to_find)
    print(f"Значение {value_to_find} найдено по индексу: {index}")
except ValueError:
    print(f"Значение {value_to_find} не найдено.")

try:
    index_nf = sorted_list.index(value_not_found)
    print(f"Значение {value_not_found} найдено по индексу: {index_nf}")
except ValueError:
    print(f"Значение {value_not_found} не найдено.")

Вывод: Для больших отсортированных списков всегда предпочтительнее использовать бинарный поиск через модуль bisect из-за его значительно лучшей производительности (O(log n) против O(n)). Оператор in и метод index() удобны для небольших списков или когда производительность не критична, но важно помнить, что они не оптимизированы для отсортированных данных и выполняют полный перебор.

Ответ 18+ 🔞

Смотри, ну вот сидишь ты с отсортированным списком, как с чистым листом, и думаешь: "Как бы мне найти тут значение, чтобы не облажаться?" А вариантов-то, блядь, как грязи, но не все одинаково годные, ёпта.

Вот, например, самый топовый способ — это бинарный поиск через bisect. Это когда ты не ломёшься вперёд, как танк, а делишь список пополам, как умный человек. Сложность у него O(log n), что для больших списков — просто песня, а не алгоритм. Мозгов, правда, надо чуть больше, чем для линейного поиска.

import bisect

sorted_list = [10, 20, 30, 40, 50, 60, 70, 80, 90]
value_to_find = 50
value_not_found = 55

# Ищем то, что есть
index = bisect.bisect_left(sorted_list, value_to_find)
if index < len(sorted_list) and sorted_list[index] == value_to_find:
    print(f"Значение {value_to_find} найдено по индексу: {index}")
else:
    print(f"Значение {value_to_find} не найдено.")

# Ищем то, чего нет (спойлер: не найдём)
index_nf = bisect.bisect_left(sorted_list, value_not_found)
if index_nf < len(sorted_list) and sorted_list[index_nf] == value_not_found:
    print(f"Значение {value_not_found} найдено по индексу: {index_nf}")
else:
    print(f"Значение {value_not_found} не найдено.")

А теперь способ для ленивых — оператор in. Просто пишешь if value in list, и вроде бы всё ок. Но, сука, он же делает линейный поиск, O(n), и ему похуй, что список отсортирован! Он будет честно ползти от начала до конца, как Герасим за Муму. Для маленьких списков сойдёт, а на больших — просто пиздец как медленно.

sorted_list = [10, 20, 30, 40, 50]
value_to_find = 30

if value_to_find in sorted_list:
    print(f"Значение {value_to_find} присутствует в списке.")
else:
    print(f"Значение {value_to_find} отсутствует в списке.")

Ну и третий вариант — метод list.index(). Тоже линейный поиск, O(n), тоже не использует сортировку. Зато если найдёт — вернёт индекс, а если нет — выебет тебя ValueError прямо в сраку. Красота!

sorted_list = [10, 20, 30, 40, 50]
value_to_find = 40
value_not_found = 100

try:
    index = sorted_list.index(value_to_find)
    print(f"Значение {value_to_find} найдено по индексу: {index}")
except ValueError:
    print(f"Значение {value_to_find} не найдено.")

try:
    index_nf = sorted_list.index(value_not_found)
    print(f"Значение {value_not_found} найдено по индексу: {index_nf}")
except ValueError:
    print(f"Значение {value_not_found} не найдено.")

Итог, блядь: если список большой и отсортирован — бери bisect, не мучайся. Это как ехать на метро, а не пешком через весь город. in и index() — это для мелких разборок, когда неохота заморачиваться. Но помни: за удобство иногда платишь скоростью, в рот меня чих-пых!

© ХакСобесов, 2026
support@hacksobesov.com