Бинарный поиск - это алгоритм поиска элемента в упорядоченном массиве данных. Алгоритм заключается в сравнении искомого элемента с элементом в середине массива, после чего массив разбивается на две части - левую и правую. Если искомый элемент меньше элемента в середине, поиск продолжается в левой части массива, а если больше - в правой. Этот процесс повторяется до тех пор, пока не будет найден искомый элемент.
Для реализации бинарного поиска в Python сначала нужно определить функцию, принимающую в качестве аргументов упорядоченный список и искомый элемент:
def binary_search(arr, x):
Следующим шагом является определение начального и конечного индексов массива. Начальный индекс - это всегда 0, а конечный - это индекс последнего элемента в массиве. Для нахождения последнего элемента массива можно использовать функцию len():
def binary_search(arr, x):
first = 0
last = len(arr) - 1
Далее в цикле while происходит сравнение элемента в середине массива с искомым элементом. Если они равны, функция возвращает индекс найденного элемента. Если искомый элемент меньше элемента в середине, конечный индекс принимает значение индекса элемента левее середины, иначе - правее середины:
def binary_search(arr, x):
first = 0
last = len(arr) - 1
while first <= last:
mid = (first + last) // 2
if arr[mid] == x:
return mid
elif x < arr[mid]:
last = mid - 1
else:
first = mid + 1
Если искомый элемент не найден, функция возвращает значение None:
def binary_search(arr, x):
first = 0
last = len(arr) - 1
while first <= last:
mid = (first + last) // 2
if arr[mid] == x:
return mid
elif x < arr[mid]:
last = mid - 1
else:
first = mid + 1
return None
Пример использования функции бинарного поиска:
arr = [1, 3, 5, 7, 9]
x = 5
result = binary_search(arr, x)
if result is not None:
print(f"Element {x} is present at index {result}")
else:
print("Element is not present in array")
Вывод: Element 5 is present at index 2
Бинарный поиск имеет логарифмическую временную сложность O(log n), что делает его более эффективным, чем линейный поиск. Однако для использования бинарного поиска массив должен быть упорядоченным, что может потребовать дополнительного времени и ресурсов на сортировку массива.