Напиши бинарный поиск на языке питон
- User
Напиши бинарный поиск на языке питон
- Assistant
Конечно! Вот пример реализации бинарного поиска на языке Python. Я приведу как итеративный, так и рекурсивный варианты.
Итеративный вариант
def binary_search_iterative(arr, target): """ Выполняет бинарный поиск в отсортированном массиве. :param arr: Отсортированный список элементов :param target: Элемент, который ищется :return: Индекс элемента, если найден, иначе -1 """ left = 0 right = len(arr) - 1 while left <= right: mid = left + (right - left) // 2 # Находим середину if arr[mid] == target: return mid # Элемент найден elif arr[mid] < target: left = mid + 1 # Ищем в правой половине else: right = mid - 1 # Ищем в левой половине return -1 # Элемент не найден # Пример использования if __name__ == "__main__": массив = [1, 3, 5, 7, 9, 11, 13, 15] искомый_элемент = 7 результат = binary_search_iterative(массив, искомый_элемент) if результат != -1: print(f"Элемент найден на индексе {результат}.") else: print("Элемент не найден.")Рекурсивный вариант
def binary_search_recursive(arr, target, left, right): """ Выполняет бинарный поиск в отсортированном массиве рекурсивно. :param arr: Отсортированный список элементов :param target: Элемент, который ищется :param left: Левый индекс диапазона поиска :param right: Правый индекс диапазона поиска :return: Индекс элемента, если найден, иначе -1 """ if left > right: return -1 # Элемент не найден mid = left + (right - left) // 2 if arr[mid] == target: return mid # Элемент найден elif arr[mid] < target: return binary_search_recursive(arr, target, mid + 1, right) # Ищем в правой половине else: return binary_search_recursive(arr, target, left, mid - 1) # Ищем в левой половине # Пример использования if __name__ == "__main__": массив = [2, 4, 6, 8, 10, 12, 14, 16] искомый_элемент = 10 результат = binary_search_recursive(массив, искомый_элемент, 0, len(массив) - 1) if результат != -1: print(f"Элемент найден на индексе {результат}.") else: print("Элемент не найден.")Пояснения
-
Предусловия: Бинарный поиск применим только к отсортированным массивам. Убедитесь, что ваш список отсортирован перед использованием этого алгоритма.
-
Итеративный подход: Использует цикл
whileдля сужения диапазона поиска до тех пор, пока элемент не будет найден или диапазон не станет пустым. -
Рекурсивный подход: Функция вызывает саму себя, уменьшая диапазон поиска на каждом шаге. Основание рекурсии — когда элемент найден или диапазон становится пустым.
-
Возвращаемое значение: В обоих случаях функция возвращает индекс найденного элемента или
-1, если элемент отсутствует в массиве.
Надеюсь, это поможет вам реализовать бинарный поиск в ваших проектах на Python!
-