Стрілки або пробіл — перемикання · F — повний екран · T — проєкторна тема · ? — підказка
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 елементів?
Що поверне функція, якщо елемента немає?