Ми розділили набір елементів на дві половини в двійковому пошуку, щоб зменшити кількість прямих порівнянь, необхідних для виявлення елемента. Однак є одна вимога: елементи масиву повинні бути попередньо відсортовані.

Двійковий пошук

The Двійковий пошук Метод знаходить індекс певного члена списку. Це один з найпопулярніших і найшвидших алгоритмів. Щоб процедура бінарного пошуку працювала, записи в списку мають бути відсортовані.

Двійковий пошук є більш ефективним методом пошуку для визначення індексу елемента, ніж Лінійний пошук оскільки нам не потрібно перевіряти кожен індекс списку.

Усю операцію алгоритму бінарного пошуку можна підсумувати наступними кроками:

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

Рекурсивний двійковий пошук

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

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

1. Для рекурсивного підходу необхідний базовий випадок.
2. У рекурсивному підході має бути рекурсивний тестовий приклад.
3. Рекурсивний підхід має бути ближчим до базового випадку.

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

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

Код

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

Вихід:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

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