Бинарный поиск в Python
Python3 ПримерыБинарный поиск — это алгоритм поиска для нахождения определённого элемента в отсортированном массиве. Процесс поиска начинается со среднего элемента массива. Если средний элемент оказался искомым элементом, процесс поиска завершается. Если искомый элемент больше или меньше среднего элемента, поиск продолжается в той половине массива, элементы которой больше или меньше среднего элемента, и, как и в начале, сравнение начинается со среднего элемента. Если на каком-то шаге массив становится пустым, это означает, что элемент не найден. Этот алгоритм поиска уменьшает область поиска вдвое при каждом сравнении.
Пример: рекурсия
# Возвращает индекс x в arr или -1, если он не существует
def binarySearch (arr, l, r, x):
# Базовая проверка
if r >= l:
mid = int(l + (r - l)/2)
# Элемент находится точно на средней позиции
if arr[mid] == x:
return mid
# Если элемент меньше элемента в средней позиции, нужно сравнивать только элементы слева
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Если элемент больше элемента в средней позиции, нужно сравнивать только элементы справа
else:
return binarySearch(arr, mid+1, r, x)
else:
# Не найдено
return -1
# Тестовый массив
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Вызов функции
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Индекс элемента в массиве равен %d" % result )
else:
print ("Элемент отсутствует в массиве")
Выполнение приведенного выше кода дает следующий вывод:
元素在数组中的索引为 3Другие расширения