Последние новости:

Поиск по сайту:

Для того, чтобы жить как следует, надо иметь или разум, или петлю (Диоген).

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

FavoriteLoadingДобавить в избранное
03.06.2021
Python 3 - Обзор

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

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

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

 

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

  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} отсутствует в массиве")

 

Читать  Пошаговое руководство по возврату к старым версиям Python

Вывод

Элемент 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), потому что в алгоритме мы выполняем поиск на месте.

 

Заключение

Двоичный поиск — один из лучших и эффективных алгоритмов поиска. Временная и пространственная сложность двоичного поиска также очень низкая; единственное предварительное условие для двоичного поиска — входной массив должен быть отсортирован в порядке возрастания.

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
Поделиться в соц. сетях:

0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
guest

**ссылки nofollow

0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии

Это может быть вам интересно

Статьи партнеров:

Рекомендуемое
Миникомпьютер - это полноценный компьютер. Это компьютер, который можно положить в…
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить

Спасибо! Ваша заявка принята

close

Спасибо! Ваша заявка принята

close