Бінарний пошук на Python: Візуальний вступ

Ласкаво просимо

У цій статті ви дізнаєтесь, як працює алгоритм двійкового пошуку та як ви можете реалізувати його на Python.

Зокрема, ви дізнаєтесь:

  • Як алгоритм працює за кадром, щоб знайти цільовий елемент.
  • Як працює його реалізація Python, рядок за рядком.
  • Чому це дуже ефективний алгоритм порівняно з лінійним пошуком.
  • Його переваги та вимоги.

Давайте почнемо! ✨

Вступ до двійкового пошуку

Цей алгоритм використовується для пошуку елемента в упорядкованій послідовності (наприклад: списку, кортежу або рядка).

Вимоги

Щоб застосувати алгоритм двійкового пошуку до послідовності, послідовність вже повинна бути відсортована за зростанням. В іншому випадку алгоритм не знайде правильної відповіді. Якщо це станеться, це буде за випадковою випадковістю.

💡 Порада: Ви можете відсортувати послідовність перед застосуванням двійкового пошуку за допомогою алгоритму сортування, який відповідає вашим потребам.

Вхід і вихід

Алгоритму (реалізованому як функція) потрібні ці дані:

  • Впорядкована послідовність елементів (наприклад: список, кортеж, рядок).
  • Цільовий елемент, який ми шукаємо.

Він повертає індекс елемента, який ви шукаєте, якщо його знайдено. Якщо елемент не знайдено, повертається -1.

Ефективність

Це дуже ефективно порівняно з лінійним пошуком (пошук елемента по одному, починаючи з першого), оскільки ми можемо «відкинути» половину списку на кожному кроці.

Почнемо занурюватися в цей алгоритм.

🔸 Візуальне покрокове керівництво

Ми застосуємо алгоритм двійкового пошуку до цього списку:

💡 Порада. Зверніть увагу, що список уже відсортований. Він включав показники як візуальну довідку.

Мета

Ми хочемо знайти індекс цілого числа 67 .

Інтервал

Давайте зробимо вигляд, що ми є алгоритмом. Як розпочати процес?

Ми починаємо з вибору двох меж інтервалу, де ми хочемо шукати. Ми хочемо здійснити пошук у всьому списку, тому ми вибираємо індекс 0як нижню межу та індекс 5як верхню межу:

Середній елемент

Тепер нам потрібно знайти індекс середнього елемента в цьому інтервалі. Ми робимо це, додаючи нижню межу та верхню межу, і ділимо результат на 2, використовуючи ціле ділення.

У цьому випадку (0 + 5)//2це 2тому, що результат ділення 5/2is 2.5і ціле число поділяє десяткову частину.

Отже, середній елемент знаходиться під індексом 2 , а середній елемент - це число 6 :

Порівняння

Тепер нам потрібно розпочати порівняння середнього елемента з нашим цільовим елементом, щоб побачити, що нам потрібно робити далі.

Ми просимо:

Чи дорівнює середній елемент елементу, який ми шукаємо?

6 == 67 # False

Ні, це не так.

Тому ми запитуємо:

Чи середній елемент більший за той елемент, який ми шукаємо?

6 > 67 # False

Ні, це не так.

Отже, середній елемент менше елемента, який ми шукаємо.

6 < 67 # True

Відкинути елементи

Оскільки список уже відсортований, це говорить нам про щось надзвичайно важливе. Це говорить нам про те, що ми можемо "відкинути" нижню половину списку, оскільки знаємо, що всі елементи, що стоять перед середнім елементом, будуть меншими за елемент, який ми шукаємо, тому нашого цільового елемента немає.

Почніть спочатку - Виберіть межі

Що нам робити далі? Ми відкинули елементи, і цикл повторюється знову.

Ми повинні вибрати межі для нового інтервалу (див. Нижче). Але зверніть увагу, що верхня межа зберігається цілою, і змінюється лише нижня межа.

Це тому, що елемент, який ми шукаємо, міг бути у верхній половині списку. Верхня межа зберігається незмінною, а нижня межа змінюється, щоб "зменшити" інтервал до інтервалу, де міг бути знайдений наш цільовий елемент.

💡 Порада: Якби середній елемент був більшим, ніж той, який ми шукаємо, верхня межа була б змінена, а нижня - збережена. Таким чином, ми відкинемо верхню половину списку і продовжимо пошук у нижній половині.

Середній елемент

Тепер нам потрібно знайти індекс середнього елемента, додавши нижню межу до верхньої межі та розділивши результат на 2, використовуючи ціле ділення.

Результатом (3+5)//2є 4, отже, середній елемент знаходиться в індексі,4 а середній - 67 .

Порівняння

Ми просимо:

Чи дорівнює середній елемент елементу, який ми шукаємо?

67 == 67 # True

Так! Отже, ми знайшли елемент за індексом 4 . Повертається значення 4, і алгоритм успішно завершено.

💡 Порада: Якби елемент не був знайдений, процес продовжувався б, доки інтервал більше не був дійсним. Якби елемент не був знайдений у всьому списку, було б повернуто -1.

Walk Проходження коду

Тепер, коли у вас є візуальна інтуїція того, як алгоритм працює за кадром, давайте зануримося в ітеративну реалізацію Python, проаналізувавши її рядком за рядком:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Заголовок

Тут ми маємо заголовок функції:

def binary_search(data, elem):

Це бере два аргументи:

  • Впорядкована послідовність елементів (наприклад: список, кортеж або рядок).
  • Елемент, який ми хочемо знайти.

Початковий інтервал

Наступний рядок задає початкову нижню та верхню межі:

low = 0 high = len(data) - 1

Початкова нижня межа - індекс, 0а початкова верхня межа - останній індекс послідовності.

Петля

Ми будемо повторювати процес, поки є дійсний інтервал, тоді як нижня межа менша або дорівнює верхній.

while low <= high:

💡 Порада. Пам’ятайте, що межі - це показники.

Середній елемент

На кожній ітерації нам потрібно знайти індекс середнього елемента. Для цього ми додаємо нижню та верхню межі та ділимо результат на 2, використовуючи ціле ділення.

middle = (low + high)//2

💡 Порада. Ми використовуємо ціле ділення на випадок, якщо список або інтервал містить парну кількість елементів. Наприклад, якби список містив 6 елементів, і ми не використовували ціле ділення, middleрезультатом (0 + 5)/2якого є 2.5. Індекс не може бути плаваючим, тому ми скорочуємо десяткову частину, використовуючи //та виділяючи елемент в індексі 2.

Порівняння

За допомогою цих умовних умов (див. Нижче) ми визначаємо, що робити залежно від значення середнього елемента data[middle]. Ми порівнюємо його з цільовим елементом, який ми шукаємо.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Є три варіанти:

  • Якщо середній елемент дорівнює елементу, який ми шукаємо, ми негайно повертаємо індекс, оскільки ми знайшли елемент.
if data[middle] == elem: return middle
  • Якщо середній елемент більше, ніж елемент, який ми шукаємо, ми перепризначаємо верхню межу, оскільки знаємо, що цільовий елемент знаходиться в нижній половині списку.
elif data[middle] > elem: high = middle - 1
  • В іншому випадку залишається єдиний варіант, що середній елемент менше, ніж елемент, який ми шукаємо, тому ми перепризначаємо нижню межу, оскільки знаємо, що цільовий елемент знаходиться у верхній половині списку.
else: low = middle + 1

Елемент не знайдено

Якщо цикл завершено без знаходження елемента, повертається значення -1.

return -1

і ми маємо остаточну реалізацію алгоритму двійкового пошуку:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

🔸 Особливі випадки

Ось деякі конкретні випадки, які ви можете виявити, починаючи працювати з цим алгоритмом:

Повторювані елементи

Якщо елемент, який ви шукаєте, повторюється у послідовності, повернутий індекс буде залежати від кількості елементів та послідовності операцій, які алгоритм виконує над послідовністю.

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

Елемент не знайдено

Якщо елемент не знайдено, повертається -1.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Порожня послідовність

Якщо послідовність порожня, буде повернуто -1.

>>> b = [] >>> binary_search(b, 8) -1

Несортована послідовність

Якщо послідовність не відсортована, відповідь буде неправильною. Отримання правильного індексу - це чистий збіг обставин, і це може бути пов’язано з порядком елементів у послідовності та послідовністю операцій, що виконуються алгоритмом.

Цей приклад повертає правильний результат:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

Але цей не робить:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

💡 Порада. Подумайте, чому перший приклад повертає правильний результат. Підказка: Це абсолютно випадковий випадок, що порядок елементів змушує алгоритм досягти правильного індексу, але покроковий процес оцінює 0, потім 2і нарешті 6. У цьому конкретному випадку для цього конкретного елемента знайдено правильний індекс, навіть якщо послідовність не відсортована.

🔹 Більш складний приклад

Тепер, коли ви більше знайомі з алгоритмом та його реалізацією на Python, тут ми маємо більш складний приклад:

Ми хочемо знайти індекс елемента 45 у цьому списку за допомогою двійкового пошуку:

Перша ітерація

Вибираються нижня та верхня межі:

Вибрано середній елемент ( 26 ):

Але середній елемент ( 26 ) - це не той елемент, який ми шукаємо, він менше 45 :

Друга ітерація

Тож ми можемо відкинути всі елементи, які менші за середній елемент, і вибрати нові межі. Нова нижня межа ( 27 ) - це елемент, розташований безпосередньо праворуч від попереднього середнього елемента:

💡 Порада. Пам’ятайте, що список уже відсортований.

Вибрано новий середній елемент ( 30 ):

Середній елемент ( 30 ) - це не той елемент, який ми шукаємо, він менше 45 :

Третя ітерація

Ми можемо відкинути елементи, які менше або дорівнюють 30, які ще не були відкинуті. Нижня межа оновлена ​​до 32 :

Тут ми маємо цікавий випадок: середній елемент є однією з меж поточного інтервалу, оскільки (7+8)//2є 7.

Середній елемент ( 32 ) - це не той елемент, який ми шукаємо ( 45 ), він менший.

Четверта ітерація

Ми можемо відкинути елементи, які менше або дорівнюють 32, які ще не були відкинуті.

Тут ми маємо ще один дуже цікавий випадок: інтервал має лише один елемент.

💡 Порада: Цей інтервал є дійсним, оскільки ми написали цю умову while high <= low:, яка включає інтервали, де індекс нижньої межі дорівнює індексу верхньої межі.

Середній елемент є єдиним елементом в інтервалі, оскільки (8+8)//2є 8, отже, індекс середнього елемента дорівнює 8, а середній елемент - 45 .

Тепер середній елемент - це той елемент, який ми шукаємо, 45 :

Тож повертається значення 8 (індекс):

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

🔸 Додаткова практика

Якщо ви хочете отримати додаткову практику з цим алгоритмом, спробуйте пояснити, як алгоритм працює за кадром, коли він застосовується до цього списку, щоб знайти ціле число 90 :

[5, 8, 15, 26, 38, 56]
  • Що відбувається поетапно?
  • Яке значення повертається?
  • Чи знайдено елемент?

Дуже сподіваюся, вам сподобалась моя стаття і вона вам допомогла. Тепер ви можете реалізувати алгоритм двійкового пошуку в Python. Ознайомтесь із моїм онлайн-курсом "Алгоритми пошуку та сортування Python: практичний підхід". Слідуйте за мною у Twitter. ⭐️