Лінійний і бінарний пошук

Структури даних і алгоритми в Python

Miriam Antona

Software engineer

Алгоритми пошуку

Пошук — базова операція
- Є кілька способів
Алгоритми пошуку елемента в колекції:
- Лінійний пошук
- Бінарний пошук

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

Перебір кожного елемента

Схематичне зображення списку невпорядкованих чисел.

Елемент знайдено
- алгоритм зупиняється
- повертає результат
Елемент не знайдено
- алгоритм продовжується

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

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

Лінійний пошук — складність

Складність: $O(n)$

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел.

15 ???

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінна first, що вказує на першу позицію списку.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінна first, що вказує на першу позицію, і змінна last, що вказує на останню позицію.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінні first і last, що вказують на першу й останню позиції, та змінна middle, що вказує на середину.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінні first, last і middle. Число 12 посередині виділене жовтим.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінна first, що вказує на першу позицію, змінна last, що вказує на позицію «середина мінус один», і змінна middle, що вказує на середину. Елементи між first і middle виділені зеленим.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінні first, last і middle. Число 12 посередині виділене жовтим.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Є змінна first, що вказує на «середина плюс один», змінна last, що вказує на останню позицію, і змінна middle, що вказує на середину. Елементи між first і middle виділені зеленим.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Вказівник middle змістився і вказує на елемент між first і last. Елементи між first і middle виділені зеленим.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Вказівник middle змістився і вказує на елемент між first і last. Елементи між first і middle виділені зеленим. Елемент 17, на який вказує middle, буде порівняно з числом 15.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Вказівник last зміщено і він вказує на те саме число, що й first.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Вказівник middle зміщено й він вказує на те саме число, що й first і last.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Вказівники first, last і middle вказують на одне й те саме число 15, яке буде порівняно з числом 15.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бінарний пошук

Працює лише для впорядкованих списків

Схематичне зображення списку впорядкованих чисел. Число 15 обведене.

15 ???
Порівняйте search_value з елементом у середині списку

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

Бінарний пошук — складність

Складність: $O(\log{}n)$

Графічне порівняння лінійного та бінарного пошуку.

Давайте потренуємось!

Структури даних і алгоритми в Python