Как реализовать алгоритм бинарного поиска?

Пользователь

от evalyn.barrows , в категории: Другие , 6 месяцев назад

Как реализовать алгоритм бинарного поиска?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

2 ответа

Пользователь

от richard , 6 месяцев назад

@evalyn.barrows 

Для реализации алгоритма бинарного поиска вам потребуется следующий код на языке Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1


Вызов функции binary_search(arr, target) возвращает индекс искомого элемента target в отсортированном списке arr. Если элемент не найден, функция возвращает -1.


Пояснение к коду:

  1. Устанавливаем начальные значения индексов low и high на краях списка arr.
  2. Входим в цикл while, который выполняется, пока индекс low меньше или равен индексу high.
  3. Вычисляем средний индекс mid с помощью формулы (low + high) // 2.
  4. Если значение элемента arr[mid] равно искомому target, возвращаем mid.
  5. Если значение элемента arr[mid] меньше искомого target, обновляем значение low на mid + 1 для продолжения поиска в правой половине списка arr.
  6. Если значение элемента arr[mid] больше искомого target, обновляем значение high на mid - 1 для продолжения поиска в левой половине списка arr.
  7. Если цикл while завершается без успешного нахождения элемента, возвращаем -1.


Пример использования функции:

1
2
3
4
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result_index = binary_search(arr, target)
print(result_index)  # Вывод: 5


Пользователь

от cierra , 9 дней назад

@evalyn.barrows 

Для использования алгоритма бинарного поиска вам нужно удостовериться, что список arr, в котором вы ищете элемент, отсортирован по возрастанию. После этого вызовите вашу функцию binary_search(arr, target) с указанием списка и целевого элемента для поиска.


Приведу пример использования алгоритма бинарного поиска на уже отсортированном списке:

1
2
3
4
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result_index = binary_search(arr, target)
print(result_index)  # Вывод: 5


В этом примере алгоритм найдет целевой элемент 23 в списке arr и вернет его индекс, который равен 5.


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