Пошук
Лінійний пошук
Бінарний пошук
Масив і шукане число
Кроки залежно від n
лінійний, найгірше: nбінарний, найгірше: ⌊log₂ n⌋ + 1ваш поточний пошук
Як рахує модель
Крок – одне порівняння шуканого числа з елементом масиву.
Лінійний: i = 0, 1, 2, … доки a[i] ≠ x. Найгірше – n кроків, у середньому ≈ n/2. Масив не мусить бути впорядкованим.
Бінарний: межі [ліво; право], mid = ⌊(ліво + право) / 2⌋. Якщо a[mid] < x – ліво = mid + 1, якщо більше – право = mid − 1. Найгірше ⌊log₂ n⌋ + 1 кроків.
Умова бінарного пошуку: масив упорядкований. Сортування коштує O(n log n), тож воно окупається, коли шукаємо багато разів.
Що спробувати
- Шукайте перший елемент масиву. Хто виграв і чому це не означає, що лінійний пошук кращий?
- Шукайте останній елемент і число, якого немає. Скільки кроків знадобилося кожному?
- Подвоюйте n: 8 → 16 → 32 → 64. На скільки зростає найгірша кількість кроків бінарного пошуку?
- Скільки кроків бінарного пошуку потрібно для телефонної книги на 1 000 000 записів? Перевірте за таблицею.
- Гра «вгадай число від 1 до 100» – це бінарний пошук. Скільки спроб завжди достатньо?
Чому так?
Кожен крок бінарного пошуку відкидає половину кандидатів: n → n/2 → n/4 → … → 1. Скільки разів можна поділити n навпіл – це і є log₂ n. Тому мільйон елементів переглядаються за 20 кроків, а мільярд – за 30.
Лінійний пошук простіший і працює на будь-якому масиві, але його час росте пропорційно n: удвічі більше даних – удвічі довше.
Шкільна програма: інформатика, 8–11 клас (алгоритми пошуку, складність алгоритмів).