ПРОГРАМА PYTHON ДЛЯ БІНАРНОГО ПОШУКУ (РЕКУРСИВНИЙ ТА ІТЕРАТИВНИЙ)

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

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

Програма Python для бінарного пошуку з використанням рекурсивного

Python3

# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> > # Check base case> > if> high>> => low:> > mid> => (high> +> low)> /> /> 2> > # If element is present at the middle itself> > if> arr[mid]> => => x:> > return> mid> > # If element is smaller than mid, then it can only> > # be present in left subarray> > elif> arr[mid]>x:> > return> binary_search(arr, low, mid> -> 1> , x)> > # Else the element can only be present in right subarray> > else> :> > return> binary_search(arr, mid> +> 1> , high, x)> > else> :> > # Element is not present in the array> > return> -> 1> # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> # Function call> result> => binary_search(arr,> 0> ,> len> (arr)> -> 1> , x)> if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

Вихід

Element is present at index 3

Часова складність : O(log n)

Допоміжний простір : O(logn) [ПРИМІТКА: рекурсія створює стек викликів]

Програма Python для бінарного пошуку з використанням ітерації

Python3

# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> > low> => 0> > high> => len> (arr)> -> 1> > mid> => 0> > while> low <> => high:> > mid> => (high> +> low)> /> /> 2> > # If x is greater, ignore left half> > if>

arr[mid]   low = mid + 1  # If x is smaller, ignore right half  elif arr[mid]>x: high = mid - 1 # означає, що x присутній у mid else: return mid # Якщо ми досягнемо цього місця, значить елемент відсутній return -1 # Тестовий масив arr = [ 2, 3, 4, 10, 40 ] x = 10 # Результат виклику функції = binary_search(arr, x) якщо результат != -1: print('Елемент присутній в індексі', str(результат)) else: print('Елемент відсутній в масиві ')>

Вихід

Element is present at index 3

Часова складність : O(log n)

Допоміжний простір : O(1)

Програма Python для бінарного пошуку з використанням вбудованого модуля bisect

Покроковий підхід:

Код імпортує модуль bisect, який забезпечує підтримку двійкового пошуку.
Визначено функцію binary_search_bisect(), яка приймає масив arr і елемент для пошуку x як вхідні дані.
Функція викликає функцію bisect_left() модуля bisect, який знаходить позицію елемента у відсортованому масиві arr, куди потрібно вставити x, щоб зберегти відсортований порядок. Якщо елемент уже присутній у масиві, ця функція поверне його позицію.
Потім функція перевіряє, чи повернений індекс i знаходиться в межах діапазону масиву та чи дорівнює елемент із цим індексом x.
Якщо умова виконується, то функція повертає індекс i як позицію елемента в масиві.
Якщо умова хибна, функція повертає -1, вказуючи, що елемент відсутній у масиві.
Потім код визначає масив arr і елемент x для пошуку.
Функція binary_search_bisect() викликається з arr і x як входами, а повернутий результат зберігається в змінній результату.
Потім код перевіряє, чи результат не дорівнює -1, вказуючи, що елемент присутній у масиві. Якщо істина, він друкує позицію елемента в масиві.
Якщо результат дорівнює -1, то код друкує повідомлення про відсутність елемента в масиві.

Python3

import> bisect> > def> binary_search_bisect(arr, x):> > i> => bisect.bisect_left(arr, x)> > if> i !> => len> (arr)> and> arr[i]> => => x:> > return> i> > else> :> > return> -> 1> > > # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> > # Function call> result> => binary_search_bisect(arr, x)> > if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

Вихід