Бинарный поиск: Общая информация
Бинарный поиск - алгоритм поиска элемента в ОТСОРТИРОВАННОМ массиве.
___
Суперважно запомнить, что бинарный поиск работает в ОТСОРТИРОВАННОМ массиве. Это признак применения данного алгоритма (ну и по-другому не будет работать).
___
Сложность алгоритма: O(log n).
Принцип работы максимально прост:
- определяем середину массива;
- сравниваем средний элемент с искомым;
- если искомый элемент меньше, отбрасываем правую часть;
- если искомый элемент больше, отбрасываем левую часть;
- повторяем действия для оставшейся половины.
___
Перед тем как умничать, нарисуем картинку в голове, а уже потом вспомним что такое логарифм и обсудим сложность.
___
course_intro
