Лінійний і двійковий пошук
Лінійний і двійковий пошук — інтерактивний експеримент із застосунку «Алгоритми в дії», безкоштовної симуляції 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 перетворить їх на картки, тести й подкасти.