Линейный и двоичный поиск
Линейный и двоичный поиск — интерактивный эксперимент из приложения «Алгоритмы в действии», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
Линейный поиск проверяет элементы по одному, поэтому в худшем случае ему нужно n шагов — O(n). Двоичный поиск работает только на отсортированном массиве: он смотрит в середину и по результату отбрасывает целую половину. После каждого шага остаётся не больше половины, поэтому хватает не более ⌈log₂(n+1)⌉ шагов — O(log n). Для 40 элементов это 6 шагов вместо 40.
Попробуй: Задай 40 элементов и ищи последнее значение. Затем выбери число, которого нет в массиве, — сколько шагов нужно каждому поиску, чтобы это понять?
Частые вопросы
Что показывает эксперимент «Линейный и двоичный поиск»?
Линейный поиск проверяет элементы по одному, поэтому в худшем случае ему нужно n шагов — O(n). Двоичный поиск работает только на отсортированном массиве: он смотрит в середину и по результату отбрасывает целую половину. После каждого шага остаётся не больше половины, поэтому хватает не более ⌈log₂(n+1)⌉ шагов — O(log n). Для 40 элементов это 6 шагов вместо 40.
Как попробовать «Линейный и двоичный поиск»?
Задай 40 элементов и ищи последнее значение. Затем выбери число, которого нет в массиве, — сколько шагов нужно каждому поиску, чтобы это понять?
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.