Бинарный поиск в Питоне

Бинарный поиск - это эффективный алгоритм поиска элемента в отсортированном массиве или списке путем сравнения среднего элемента с целевым значением и последующим сужением диапазона поиска.

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

1. Определение функции бинарного поиска:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

2. Передача отсортированного массива и целевого значения в функцию бинарного поиска:

arr = [1, 4, 7, 10, 14, 18, 24, 30, 35, 42]
target = 18

result = binary_search(arr, target)

3. Обработка результата:

if result != -1:
    print("Элемент найден в позиции:", result)
else:
    print("Элемент не найден в массиве.")

В этом примере, мы имеем отсортированный массив arr и ищем элемент со значением 18. Функция binary_search будет делить диапазон поиска пополам и сравнивать значение в середине с искомым значением.

Если значение в середине равно искомому значению, то возвращается позиция этого значения в массиве. Если значение в середине меньше искомого значения, то левая граница сдвигается направо от середины. Если значение в середине больше искомого значения, то правая граница сдвигается налево от середины.

В случае, если элемент не найден, возвращается -1.

Бинарный поиск является эффективным, так как каждая итерация сокращает диапазон поиска вдвое. Это особенно полезно при работе с большими наборами данных.

Теперь вы знакомы с реализацией бинарного поиска на языке Python. Успешных вам поисковых операций!