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

@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

@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.

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