Пошук елементів у списку: in, index, лінійний і двійковий пошук
Готові засоби
a = [4, 8, 15, 16, 23, 42]
print(15 in a) # True
print(a.index(15)) # 2Якщо елемента немає, index викличе помилку ValueError, тому спершу перевіряють in.
Лінійний пошук
Перебираємо елементи по черзі, поки не знайдемо.
def linear(a, x):
for i in range(len(a)):
if a[i] == x:
return i
return -1У найгіршому разі перевіряємо всі n елементів.
Двійковий пошук
Працює лише для відсортованого списку: порівнюємо із середнім елементом і відкидаємо половину.
def binary(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Візуалізатор
У лабораторії «Алгоритми над списками» нижче можна подивитися пошук покроково: як рухається вказівник і скільки порівнянь зроблено.
Перевірте себе
Яка умова застосування двійкового пошуку?
Скільки порівнянь у найгіршому разі при лінійному пошуку в списку з 50 елементів?
Що поверне функція, якщо елемента немає?
BitMath · https://www.bitmath.com.ua/informatyka/informatyka-8-tema-6/i8-poshuk-elementiv