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

Лінійний і бінарний пошук елемента в масиві

Підказка

Що вивчимо. Як знайти елемент у масиві: лінійний і бінарний пошук.

Лінійний пошук

Перебираємо елементи по черзі, поки не знайдемо:

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.

Приклад

Гра «Вгадай число від 1 до 100»: питаючи «більше чи менше за 50?», знайдемо число не більш ніж за 7 запитань — це і є бінарний пошук.

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

  1. Чому бінарний пошук не працює в невпорядкованому масиві?

  2. Скільки кроків потрібно максимум для пошуку серед 1024 елементів бінарним методом?

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

BitMath · https://bitmath.com.ua/informatyka/informatyka-9-tema-6/i9-alhorytmy-masyviv-3