Сортировка и поиск

Отсортированные данные — половина успеха во многих задачах: в них легко найти наибольшее, одинаковые элементы оказываются рядом, а искать нужное значение можно очень быстро.

sorted и sort

a = [5, 2, 9, 1]
b = sorted(a)       # новый список [1, 2, 5, 9], a не изменился
a.sort()            # сортирует сам a, возвращает None

• sorted(что угодно) — возвращает новый список. Работает и со строкой, и с map: sorted("банан") → ['а', 'а', 'б', 'н', 'н'].
• список.sort() — сортирует список «на месте».

Частая ошибка: a = a.sort() — после этого в a окажется None.

По убыванию — параметр reverse=True:

print(sorted([3, 8, 1], reverse=True))   # [8, 3, 1]

Строки сортируются по алфавиту (точнее, по кодам символов): заглавные буквы идут раньше строчных.

Сортировка по ключу

Параметр key задаёт, по какому признаку сравнивать элементы. Ему передают функцию, которая вызывается для каждого элемента:

words = ["яблоко", "кот", "арбуз", "ёж"]
print(sorted(words, key=len))        # по длине: ['ёж', 'кот', 'арбуз', 'яблоко']

nums = [-7, 3, -1, 5]
print(sorted(nums, key=abs))         # по модулю: [-1, 3, 5, -7]

names = ["bob", "Alice", "carl"]
print(sorted(names, key=str.lower))  # без учёта регистра

Сортировка в Python устойчивая: элементы с одинаковым ключом сохраняют исходный порядок. Так, в примере выше «кот» и «ёж» имеют разную длину, а при равной длине слова остались бы в том порядке, в каком были.

key работает и в min и max: max(words, key=len) — самое длинное слово.

Свои функции для key (например, «сначала по длине, потом по алфавиту») научимся писать в теме «Функции».

Что даёт сортировка

После сортировки:

• минимум — a[0], максимум — a[-1], k-й по величине — a[-k];
• одинаковые элементы стоят рядом — их легко сосчитать, сравнивая a[i] и a[i - 1];
• соседние элементы — самые близкие по значению.

Пример: сколько различных чисел в списке?

a = sorted([4, 1, 4, 2, 1, 4])   # [1, 1, 2, 4, 4, 4]
distinct = 1
for i in range(1, len(a)):
    if a[i] != a[i - 1]:
        distinct += 1
print(distinct)                    # 3

Сортировка n элементов занимает примерно n · log n операций — список из 10⁵–10⁶ чисел сортируется за доли секунды.

Линейный поиск

Найти элемент в неотсортированном списке можно только перебором: x in a, a.index(x) или цикл. Это n шагов. Если искать нужно много раз, выходит долго.

Двоичный поиск

В отсортированном списке можно искать гораздо быстрее. Идея как в игре «угадай число от 1 до 100»: спрашиваем середину, и каждый ответ отбрасывает половину вариантов.

Найдём, есть ли число x в отсортированном списке:

a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23

lo, hi = 0, len(a) - 1
found = False
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == x:
        found = True
        break
    elif a[mid] < x:
        lo = mid + 1      # x правее середины
    else:
        hi = mid - 1      # x левее середины
print(found)              # True

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

Самое сложное в двоичном поиске — не ошибиться на единицу в границах. Поэтому для стандартных задач есть готовый модуль.

Модуль bisect

from bisect import bisect_left, bisect_right

heights = [140, 145, 150, 150, 155, 162]   # отсортировано!

print(bisect_left(heights, 150))   # 2 — сколько элементов СТРОГО меньше 150
print(bisect_right(heights, 150))  # 4 — сколько элементов МЕНЬШЕ ИЛИ РАВНЫ 150

• bisect_left(a, x) — первая позиция, куда можно вставить x, не нарушив порядок. Это и есть количество элементов < x.
• bisect_right(a, x) — позиция после всех элементов, равных x. Это количество элементов <= x.

Сколько учеников ростом от 145 до 155 включительно?

print(bisect_right(heights, 155) - bisect_left(heights, 145))   # 4

Важно: bisect работает правильно только на отсортированном списке.

Итог

• sorted(a) — новый список, a.sort() — на месте; reverse=True — по убыванию;
• key=len, key=abs, key=str.lower — сортировка по признаку; работает и в min/max;
• после сортировки одинаковые элементы рядом, а соседи — ближайшие по значению;
• двоичный поиск находит значение за log n шагов, но только в отсортированном списке;
• bisect_left — сколько элементов < x, bisect_right — сколько <= x.