Бинарный поиск — это алгоритм поиска, используемый для поиска целевых элементов в контейнере, где элементы должны быть расположены в порядке возрастания. Обычно двоичный поиск используется для поиска порядкового номера целевого элемента в отсортированном массиве.
В бинарном поиске используется подход «разделяй и властвуй», при котором массив делится на равные части до тех пор, пока не будет найден целевой элемент.
Алгоритм двоичного поиска реализуется как итеративным, так и рекурсивным оператором. Двоичный поиск более эффективен и быстрее по сравнению с линейным поиском.
Алгоритм двоичного поиска
- Отсортируйте и расположите элементы в массиве arr в порядке возрастания.
- Алгоритмы сравнивают средний элемент n с целевым элементом target .
- Алгоритм возвращает индекс позиции среднего элемента, если целевой элемент оказывается равным среднему элементу,
- Алгоритм ищет нижнюю половину массива, если целевой элемент меньше среднего элемента.
- Алгоритм ищет верхнюю половину массива, если целевой элемент больше среднего элемента.
- Алгоритм повторяет 4-й и 5-й шаги до тех пор, пока длина массива не станет равной единице или меньше 1.
В конце либо возвращается значение индекса элемента, либо элемент не существует в массиве.
Псевдокод двоичного поиска
Итеративный
function Binary_Search(arr, n, target) is left := 0 right:= n − 1 while left ≤ right do middle := floor((left + right) / 2) if arr[middle] target then right := middle − 1 else: return middle return unsuccessful
Рекурсивный
function Binary_Search(arr, left, right, target) is if right >= left middle = (left+right)//2 if arr[middle] == target return middle else if arr[middle] > tarrget return Binary_Search(arr, low, mid-1, target) else return Binary_Search(arr, mid+1, right, target) else return unsuccessful
Реализация двоичного поиска в Python
Итеративный
В итеративном подходе мы используем циклы для реализации двоичного поиска.
def Binary_Search(arr,n, target):
left = 0
right = n-1
middle=0
while left<=right:
middle = (right+left)//2
если средний элемент равен целевому элементу
if arr[middle]==target:
return middle
#если целевой элемент больше среднего
elif arr[middle]< target:
left = middle+1
# если целевой элемент меньше среднего
else: right =middle-1
# если целевой элемент отсутствует в массиве
return -1
if __name__ == '__main__':
# отсортированный массив
sorted_arr = [0,4,7,10,14,23,45,47,53]
# длина массива
n = len(sorted_arr)
# элемент для поиска
target = 47
position = Binary_Search(sorted_arr, n,target)
if position != -1:
print(f"Элемент {target} присутствует в индексе {position}")
else:
print(f"Элемент {target} отсутствует в массиве")
Вывод
Элемент 47 присутствует в индексе 7
Рекурсивный
В рекурсивном режиме вместо использования цикла мы продолжаем вызывать функцию снова и снова, пока не будет выполнено базовое условие.
def Binary_Search(arr,left,right ,target):
# базовое условие
if righttarget:
return Binary_Search(arr, left, middle-1, target)
# если целевой элемент меньше среднего элемента
else:
return Binary_Search(arr, middle+1, right, target)
if __name__ == '__main__':
# отсортированный массив
sorted_arr = [0,4,7,10,14,23,45,47,53]
left=0
right = len(sorted_arr)-1
# элемент для поиска
target = 47
position = Binary_Search(sorted_arr, left, right,target)
if position != -1:
print(f"Элемент {target} присутствует в индексе {position}")
else :
print(f"Элемент {target} отсутствует в массиве")
Вывод
Элемент 90 отсутствует в массиве
Сложность
Бинарный поиск имеет временную сложность O(log n), где n — количество элементов, присутствующих в массиве.
Бинарный поиск имеет пространственную сложность O(1), потому что в алгоритме мы выполняем поиск на месте.
Заключение
Двоичный поиск — один из лучших и эффективных алгоритмов поиска. Временная и пространственная сложность двоичного поиска также очень низкая; единственное предварительное условие для двоичного поиска — входной массив должен быть отсортирован в порядке возрастания.