Что такое двоичный поиск?

Бинарный поиск – это алгоритм поиска, используемый для поиска целевых элементов в контейнере, где элементы должны быть расположены в порядке возрастания. Обычно двоичный поиск используется для поиска порядкового номера целевого элемента в отсортированном массиве.

В бинарном поиске используется подход «разделяй и властвуй», при котором массив делится на равные части до тех пор, пока не будет найден целевой элемент.

Алгоритм двоичного поиска реализуется как итеративным, так и рекурсивным оператором. Двоичный поиск более эффективен и быстрее по сравнению с линейным поиском.

Алгоритм двоичного поиска

1. Отсортируйте и расположите элементы в массиве arr в порядке возрастания.
2. Алгоритмы сравнивают средний элемент n с целевым элементом target .
3. Алгоритм возвращает индекс позиции среднего элемента, если целевой элемент оказывается равным среднему элементу,
4. Алгоритм ищет нижнюю половину массива, если целевой элемент меньше среднего элемента.
5. Алгоритм ищет верхнюю половину массива, если целевой элемент больше среднего элемента.
6. Алгоритм повторяет 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 отсутствует в массиве