Лінійний і бінарний пошук елемента в масиві
Лінійний пошук
Перебираємо елементи по черзі, поки не знайдемо:
def linear_search(a, x):
for i in range(len(a)):
if a[i] == x:
return i
return -1
print(linear_search([5, 3, 9, 1], 9)) # 2
print(linear_search([5, 3, 9, 1], 7)) # -1Працює для будь-якого масиву. У гіршому разі — n порівнянь.
Бінарний пошук
Працює лише для впорядкованого масиву. Дивимося на середній елемент і відкидаємо половину:
def binary_search(a, x):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == x:
return mid
if a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1
a = [1, 3, 5, 9, 12, 20, 31]
print(binary_search(a, 12)) # 4Скільки кроків
Розмір масиву | Лінійний (гірший) | Бінарний |
|---|---|---|
10 | 10 | 4 |
1 000 | 1 000 | 10 |
1 000 000 | 1 000 000 | 20 |
Кожен крок бінарного пошуку зменшує область удвічі, тому кроків приблизно log₂ n.
Перевірте себе
Чому бінарний пошук не працює в невпорядкованому масиві?
Скільки кроків потрібно максимум для пошуку серед 1024 елементів бінарним методом?
Що повертає функція, якщо елемент не знайдено?