Двоичный поиск — это эффективный алгоритм поиска элемента в **отсортированном** массиве. Он работает за **O(log n)**, так как на каждом шаге делит диапазон поиска пополам. ### Алгоритм: - **Определяем границы** (начало и конец массива). - **Находим середину** текущего диапазона. - **Сравниваем** элемент в середине с искомым: - Если равен — возвращаем индекс. - Если меньше — смещаем левую границу. - Если больше — смещаем правую границу. - **Повторяем**, пока границы не сойдутся. ### Пример на 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 # Элемент не найден ``` ### Особенности: - Работает **только с отсортированными данными**. - Эффективнее линейного поиска (**O(n)** vs **O(log n)**). - Подходит для больших массивов. - Может быть реализован **рекурсивно** (но итеративный вариант предпочтительнее из-за отсутствия накладных расходов на вызовы).