2.
Двоичный поиск в упорядоченном массиве: начало (Python)
Двоичный поиск является эффективным алгоритмом — его оценка сложности O(log2(n)), в то время, как у обычного последовательного поиска O(n). Это значит, что, например, для массива из 1024 элементов, линейный поиск, в худшем случае, когда искомого элемента нет в массиве, обработает все 1024 элемента. Бинарным поиском достаточно обработать \(log_2(1024) = 10\) элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
Недостатками такого алгоритма является требование упорядоченности данных, а также возможность доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом, алгоритм не может работать на неупорядоченных массивах и любых структурах данных, построенных на базе связных списков.
Реализация
пока (right – left > 1) // Пока правая граница правее левой
нц
middle = (left + right) / 2; // Середина области поиска
если (A[middle] >= b), то
right = middle; // Передвигаем правую границу
иначе
left = middle; // Иначе передвигаем левую границу
кц
если (A[right] == X), то
вывод right;
иначе
вывод -1;
где:
А - исходный массив,
N - размер массива,
X - искомое число.
Реализуйте алгоритм бинарного поиска.
Формат входных данных
В первой строке входных данных содержатся натуральные числа N и K (\(0<N <= 100000,\ 0<K<=10^9\) ). Во второй строке задаются N элементов массива, отсортированного по возрастанию. Элементы массива - целые числа, каждое из которых по модулю не превосходит 109.
Формат выходных данных
Требуется для K вывести в отдельную строку его номер в массиве, если это число встречается в массиве, и "NO" в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10 5
1 2 3 4 5 6 7 8 9 10
|
5 |
В блоке вставки кода используйте 4 пробела для отступов.
Вставьте недостающие фрагменты кода
Python
def SearchBinary (arr, key):
midd = 0
left = -1
right = len(arr)
|
|
|
n, k = map(int, input().split())
arr = list(map(int, input().split()))
ind = SearchBinary(arr, k)
if ind >= 0:
print(ind+1)
else:
print('NO')
|
