З відповідями ← До сторінки

Пошук елементів у списку: in, index, лінійний і двійковий пошук

Підказка

Що вивчимо. Як знайти елемент у списку: 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
Приклад

У списку з 1 000 000 елементів лінійний пошук може потребувати до 1 000 000 порівнянь, двійковий — не більше 20 (бо 2²⁰ ≈ 10⁶).

Візуалізатор

У лабораторії «Алгоритми над списками» нижче можна подивитися пошук покроково: як рухається вказівник і скільки порівнянь зроблено.

Перевірте себе

  1. Яка умова застосування двійкового пошуку?

  2. Скільки порівнянь у найгіршому разі при лінійному пошуку в списку з 50 елементів?

  3. Що поверне функція, якщо елемента немає?

BitMath · https://bitmath.com.ua/informatyka/informatyka-8-tema-6/i8-poshuk-elementiv