Линейный поиск и бинарный поиск: простое объяснение на примерах
Это блог Петрова Данилы, присоединяйтесь к моему телеграм каналу! 🔥
Привет! Сегодня хочу рассказать про два алгоритма, способа поиска информации: линейный и бинарный.
Звучит сложно, но на деле это истории из нашей повседневной жизни!
Линейный поиск: проверяй всё подряд
Представьте, что я загадал число от 1 до 100. Вы начинаете угадывать так: «1?» — нет. «2?» — нет. «3?» — нет ... и так до самого конца.
Если моё число окажется 99, придётся сделать 99 попыток.
Вот это и есть линейный поиск: мы идём шаг за шагом и проверяем всё подряд.
📌 Жизненная ассоциация: Вы ищете имя в списке гостей, который никак не отсортирован. Придётся просмотреть каждую строчку, пока не найдёте нужное.
Бинарный поиск: режем пополам
Теперь представьте другую стратегию поиска. Я всё так же загадал число от 1 до 100, но вместо того, чтобы начинать с 1, вы сразу говорите: «50».
Если я отвечаю «меньше», вы отбрасываете все числа до 50. Если «больше», вы отбрасываете числа после 50.
Следующая догадка — середина оставшегося диапазона. Например, «75». Я говорю: «Слишком много». Значит, теперь число где-то между 51 и 74.
Так шаг за шагом вы делите количество возможных вариантов пополам и гораздо быстрее отгадываете число.
📌 Жизненная ассоциация: Вы ищете слово в словаре. Никто не листает с первой страницы до конца. Все открывают словарь примерно посередине и уже по алфавиту понимают: нужное слово раньше или позже.
Сравнение в цифрах простым языком
Если вы ищете число в отсортированном списке от 1 до 100:
- Линейным поиском — в худшем случае придётся сделать 100 попыток. Формула: максимум шагов = n, где n — количество элементов. Пример: n = 100 → максимум шагов = 100.
- Бинарным поиском — в худшем случае нужно не больше 7 попыток. Формула: максимум шагов = log₂(n), где n — количество элементов. Пример: n = 100 → log₂(100) ≈ 7.
Вам может показаться, что разница, в принципе, не большая, но что если нужно будет искать число в отсортированном списке из 240 000 чисел:
- Линейным поиском — в худшем случае до 240 000 шагов. Формула: максимум шагов = n. То есть: n = 240 000 → максимум шагов = 240 000.
- Бинарным поиском — в худшем случае около 18 шагов. Формула: максимум шагов = log₂(n). Пример: n = 240 000 → log₂(240 000) ≈ 18.
Разница колоссальная!
Также стоит помнить, что сложность алгоритма измеряется не в конкретных миллисекундах необходимых для выполнения, а в том, как меняется время выполнения при росте количества данных.
Главное, что стоит запомнить
- Линейный поиск — это самый понятный способ искать. Он подходит, когда список небольшой или элементы расположены в случайном порядке. Но если данных становится много, такой поиск может занять очень много времени.
- Бинарный поиск — работает гораздо быстрее, но только в том случае, если список отсортирован. Зато когда это условие выполняется, нужный элемент находится всего за несколько шагов, даже если список огромный.
- Сложность алгоритма измеряется не в конкретных миллисекундах необходимых для выполнения, а в том, как меняется время выполнения при росте количества данных.
А в каких ситуациях вы бы выбрали линейный поиск, а в каких бинарный? Напишите своё мнение — давайте обсудим! Жду вас там👇
Это блог Петрова Данилы, присоединяйтесь к моему телеграм каналу! 🔥