Алгоритми над списками: покроковий візуалізатор
Введіть список, оберіть алгоритм і дивіться покроково, як рухається вказівник і скільки порівнянь зроблено.
Як це працює
Алгоритм опрацювання списку проходить елементи по черзі й накопичує результат: суму, кількість, найбільше значення.
Двійковий пошук працює лише для відсортованого списку й щоразу відкидає половину елементів, тому потребує дуже мало порівнянь.
Приклади
- Двійковий пошук — відкрити з цими значеннями
- Максимум — відкрити з цими значеннями
Часті запитання
Чому двійковий пошук потребує відсортованого списку?
Бо за порівнянням із середнім елементом ми вирішуємо, у якій половині шукати далі; це можливо лише тоді, коли елементи впорядковано.
Скільки порівнянь потрібно для 1000 елементів?
Лінійний пошук у найгіршому разі — 1000, двійковий — не більше 10.
Читайте також: Пошук елементів.