Почему вас это должно волновать? Поиск — одна из наиболее распространенных операций в программировании. Предположим, у вас есть массив, содержащий 1 миллион отсортированных чисел, и вам нужно найти одно конкретное значение. Простой подход — проверить каждый элемент: 1 → 2 → 3...
Почему вас это должно волновать?
Поиск — одна из наиболее распространенных операций в программировании.
Предположим, у вас есть массив, содержащий 1 миллион отсортированных чисел, и вам нужно найти одно конкретное значение.
Простой подход — проверить каждый элемент:
1 → 2 → 3 → 4 → ...
В худшем случае вам может потребоваться проверить все 1 миллион элементов.
Но что, если бы после каждого сравнения можно было исключить половину оставшихся элементов?
Это именно то, что делает двоичный поиск.
Вместо проверки каждого элемента двоичный поиск многократно делит пространство поиска пополам.
Это дает нам:
О (логарифм n)
что значительно быстрее, чем:
О (п)
для больших наборов данных.
Проблема
Рассмотрим этот отсортированный массив:
[10, 20, 30, 40, 50, 60, 70, 80, 90]
Мы хотим найти:
70
Линейный поиск проверяет:
10
20
30
40
50
60
70
Это 7 сравнений.
Двоичный поиск использует другой подход.
Начнем с середины:
[10, 20, 30, 40, 50, 60, 70, 80, 90]
↑
50
Мы сравниваем:
70 > 50
Следовательно, мы знаем, что ответ не может быть в левой половине.
Мы отбрасываем:
10 20 30 40 50
Теперь ищите:
60 70 80 90
Проверьте середину:
60 70 80 90
↑
70
Мы нашли это.
Вместо того, чтобы проверять каждый элемент, мы исключали большие части массива на каждом этапе.