Бинарный поиск

2.1 Определение бинарного поиска и его основные концепции

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

Основные концепции:

• Отсортированный массив: Бинарный поиск работает только на отсортированных массивах.
• Деление пополам: Алгоритм сравнивает искомый элемент с элементом в середине массива.
• Рекурсивное или итеративное деление: Если искомый элемент меньше среднего, поиск продолжается в левой половине массива, иначе — в правой.
• Условие завершения: Поиск прекращается, когда элемент найден или диапазон поиска становится пустым.

Важно! Для бинарного поиска нужен отсортированный массив.

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

Пример отсортированного массива:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Пошаговая реализация бинарного поиска

Принцип работы бинарного поиска:

1. Инициализация: Установить начальные границы поиска (левая и правая границы массива).
2. Выбор среднего элемента: Найти индекс среднего элемента массива.
3. Сравнение: Сравнить средний элемент с искомым значением.
4. Обновление границ:
   1. Если средний элемент равен искомому значению, вернуть его индекс.
   2. Если искомое значение меньше среднего элемента, обновить правую границу поиска.
   3. Если больше — обновить левую границу.
5. Повторение: Повторять шаги 2-4 до нахождения элемента или пока левая граница не станет больше правой.

Пошаговый алгоритм:

1. Инициализация: Установить left на 0 и right на len(arr) - 1.
2. Вычислить средний элемент: mid = (left + right) // 2.
3. Сравнить с целевым элементом:
   1. Если arr[mid] == target, вернуть mid.
   2. Если arr[mid] < target, обновить left = mid + 1.
   3. Если arr[mid] > target, обновить right = mid - 1.
4. Повторить: Вернуться к шагу 2 до тех пор, пока left <= right.
5. Если элемент не найден: Вернуть -1

Итеративная реализация бинарного поиска в Python:

def binary_search(arr, target):
    left, right = 0, 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

# Пример использования:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 7 найден на индексе 3

2.3 Временная сложность бинарного поиска O(log n)

Бинарный поиск имеет временную сложность O(log n), где n — это количество элементов в массиве. Это означает, что на каждом шаге алгоритм делит количество элементов пополам, что значительно ускоряет поиск по сравнению с линейным поиском, имеющим временную сложность O(n).

Анализ временной сложности:

• Лучший случай (Best case): Элемент найден на первом шаге, O(1).
• Средний случай (Average case): O(log n).
• Худший случай (Worst case): Элемент найден на последнем шаге или отсутствует, O(log n).

Пример для анализа временной сложности:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Элемент {target} найден на индексе {index}")  # Вывод: Элемент 7 найден на индексе 3

# Алгоритм выполнил 3 шага (логарифм от 7 элементов) для нахождения элемента, 
# что соответствует O(log n)

Графическое представление сложности:

Представьте себе массив из 16 элементов.

Допустим, мы ищем элемент 15, тогда шаги будут такие:

Первый шаг. Проверит средний элемент (8 элементов остаётся).

Второй шаг. Проверит средний элемент в оставшейся половине (4 элемента остаётся).

Третий шаг. Проверит средний элемент в оставшейся половине (2 элемента остаётся).

Четвёртый шаг. Проверит последний элемент (1 элемент остаётся).

В результате алгоритм выполнит 4 шага для массива из 16 элементов, что соответствует логарифму по основанию 2 от 16, т.е., log2(16) = 4. Это и есть логарифмическая сложность O(log n).

2

Задача

Модуль 1: Python Core, 16 уровень, 1 лекция

Недоступна

Бинарный поиск

Бинарный поиск

Открыть

2

Задача

Модуль 1: Python Core, 16 уровень, 1 лекция

Недоступна

Поиск граничных значений

Поиск граничных значений

Открыть