- Дайте определение линейному поиску и объясните его своими словами
- Правильно используйте ключевые термины, например «линейный поиск»
- Применяйте изученное к новым примерам и вопросам
- Избегайте типичных ошибок, которые ученики допускают в этой теме
Не все решения равны: одни находят имя в списке из миллиона за двадцать шагов, а другим нужен миллион. На уровне GCSE вы переходите от написания любого работающего решения к написанию хороших. Эта глава охватывает классические алгоритмы поиска и сортировки — и то, как измерить, какой из них лучше.
Этот урок посвящён линейному поиску: находите элементы, проверяя каждый по одному.
Находите элементы, проверяя каждый по одному.
Ключевые идеи
Бинарный поиск требует отсортированных данных
Бинарный поиск намного быстрее линейного — около 20 сравнений для миллиона элементов — но он работает только если список сначала отсортирован. Сортировка тоже требует времени, поэтому для разового поиска в неотсортированных данных линейный поиск может оказаться лучше. Правильный алгоритм зависит от ситуации, а не только от теории.
Худший случай — вот что важно
Алгоритму может повезти и он найдёт цель с первой попытки, но инженеры планируют худший случай — самый медленный возможный прогон. Big-O описывает этот рост: O(n) означает, что удвоение входных данных примерно удваивает время, а O(n²) означает, что удвоение входных данных примерно учетверяет его.
Термин — линейный поиск: Проверка каждого элемента списка по одному, пока не найдена цель. Просто, работает на неотсортированных списках, но медленно на больших.
Используйте бинарный поиск, чтобы найти 7 в отсортированном списке [1, 3, 5, 7, 9, 11, 13].
low = 0, high = 6. Средний индекс = (0 + 6) // 2 = 3. Элемент с индексом 3 — это 5. 5 меньше 7, поэтому отбрасываем левую половину: low становится 4. Средний индекс = (4 + 6) // 2 = 5. Элемент с индексом 5 — это 11. 11 больше 7, поэтому отбрасываем правую половину: high становится 4. Средний индекс = (4 + 4) // 2 = 4. Элемент с индексом 4 — это 7. Найдено — 7 находится под индексом 4 всего после 3 сравнений.
Ответ: Бинарный поиск находит 7 под индексом 4 за 3 сравнения; линейному поиску понадобилось бы 4.
- Использование бинарного поиска в неотсортированном списке Исправление: сначала отсортируйте список или используйте линейный поиск — бинарный поиск в неотсортированных данных даёт неверные ответы, а не просто работает медленно.
- Забывчивость о том, что индексы списка начинаются с 0 Исправление: в списке из 7 элементов последний индекс — 6; ошибки на единицу — классическая ловушка на экзамене, поэтому разбирайте внимательно.
Практика
50 — каждый элемент должен быть проверен, если цель последняя или отсутствует.
Около 20 — каждый шаг уменьшает оставшиеся элементы вдвое, поэтому миллион сокращается до одного примерно за 20 делений пополам.
Если список не отсортирован, бинарному поиску сначала нужна сортировка — её стоимость может перевесить более быстрый поиск для разового запроса.
O(n²) — учетверение при удвоении входных данных — признак квадратичного роста.
Быстрая проверка
Что из этого лучше всего определяет "линейный поиск"?
Верно или неверно: бинарный поиск — всегда лучший алгоритм поиска.
Проследите один проход сортировки пузырьком на списке [5, 3, 8, 1]. Что будет со списком после?
- Линейный поиск: находите элементы, проверяя каждый по одному.
- Бинарный поиск требует отсортированных данных: Бинарный поиск намного быстрее линейного — около 20 сравнений для миллиона элементов — но он работает только если список сначала отсортирован.
- Бинарный поиск: Многократное деление отсортированного списка пополам для поиска цели — сравнение со средним элементом и отбрасывание половины, которая не может содержать цель.
- Остерегайтесь: использования бинарного поиска в неотсортированном списке