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

Главное

Линейный поиск — O(n), бинарный — O(log n) в отсортированном массиве. Сортировки: пузырьком, выбором, встроенная sorted.

Правила

1. Бинарный поиск — только в отсортированном
2. sorted() возвращает новый список
3. Пузырёк — соседние обмены

Разберём пример

Сколько сравнений максимум у бинарного поиска для 1 024 элементов?

10

Частые ошибки

• Применять бинарный поиск к неотсортированным данным.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.