Бинарный поиск
Представьте, что мы записали высоты всех зданий в мире в порядке возрастания. Первый элемент в этом списке — самое низкое здание в мире, а последний — самое высокое. Мы играем в игру, где, получив число-запрос, обозначающее высоту здания, нужно вернуть позицию (индекс) этого здания в списке. Если в списке нет здания запрошенной высоты, ответом будет -1.
Один из самых простых способов решения — пройтись по всему массиву с помощью цикла
for и сравнивать каждый элемент с запросом. В худшем случае это будет делать n операций для каждого запроса (если в массиве n элементов).h = [...] # Высоты всех зданий в порядке возрастания
q = int(input()) # Запрашиваемая высота
for i, height in enumerate(h):
if height == q: # Если элемент найден
print(i) # Вывести индекс
break # И остановиться
else: # Если мы не нашли здание с высотой q (else = nobreak)
print(-1) # Вывести -1, чтобы указать, что элемент не найденОднако, учитывая, что массив уже отсортирован в порядке возрастания, мы выполняем много лишних операций. Вместо того чтобы начинать с начала массива и идти к концу, мы могли бы «перепрыгивать» через ненужные элементы и гораздо быстрее находить правильный индекс.
Так как массив отсортирован по возрастанию, более быстрый метод состоит в том, чтобы смотреть на средний элемент. Если он меньше
q, мы можем отбросить всю левую половину массива и искать только в правой. Если же элемент больше q, наоборот — отбросить правую часть и искать в левой. Повторяя процедуру сравнения со средним элементом и отбрасывая ненужные половины, мы реализуем алгоритм Бинарного поиска.h = [...] # Высоты всех зданий в порядке возрастания
q = int(input()) # Запрашиваемая высота
l, r = 0, len(h) # Ответ всегда лежит в интервале [l; r). Обратите внимание, что r не включается
while r - l > 1: # Остался хотя бы один элемент для рассмотрения
mid = (l + r) // 2 # Берём средний индекс
if h[mid] > q: # h[mid] > q => отбрасываем правую половину
r = mid
else: # h[mid] <= q => отбрасываем левую половину
l = mid
# В итоге мы должны прийти к тому, что h[l] = q
print(l if h[l] == q else -1)Рассмотрим пример: пусть у нас есть массив высот зданий
h = [20, 22, 23, 23, 34, 49, 52, 55, 58], и нам нужно найти индекс здания высотой 49.Этот алгоритм сделает несколько итераций:
mid = (0 + 9) // 2 = 4⇒h[4] = 34≤49⇒ отбрасываем левую часть.
mid = (4 + 9) // 2 = 6⇒h[6] = 52>49⇒ отбрасываем правую часть.
mid = (4 + 6) // 2 = 5⇒h[5] = 49≤49⇒ отбрасываем левую часть.
l = 5,r = 6⇒r - l == 1⇒ цикл while завершается, и мы выводим 5, так какh[5] = 49.
Хотя на этом примере разница не столь заметна, представьте, что нам нужно обрабатывать 10 миллиардов зданий. Линейный поиск в худшем случае потребуется 10 миллиардов итераций, а двоичный поиск, отбрасывая половину массива за один шаг, даёт колоссальный выигрыш в производительности. Посмотрим, сколько итераций нужно, если каждый раз делить массив из 10 миллиардов элементов пополам:
Подсказка: это всего лишь 32 итерации вместо 10 миллиардов
- 10,000,000,000 / 2 = 5,000,000,000
- 5,000,000,000 / 2 = 2,500,000,000
- 1250000000 / 2 = 625000000
- 625000000 / 2 = 312500000
- 312500000 / 2 = 156250000
- 156250000 / 2 = 78125000
- 78125000 / 2 = 39062500
- 39062500 / 2 = 19531250
- 19531250 / 2 = 9765625
- 9765625 / 2 = 4882812
- 4882812 / 2 = 2441406
- 2441406 / 2 = 1220703
- 1220703 / 2 = 610351
- 610351 / 2 = 305175
- 305175 / 2 = 152587
- 152587 / 2 = 76293
- 76293 / 2 = 38146
- 38146 / 2 = 19073
- 19073 / 2 = 9536
- 9536 / 2 = 4768
- 4768 / 2 = 2384
- 2384 / 2 = 1192
- 1192 / 2 = 596
- 596 / 2 = 298
- 298 / 2 = 149
- 149 / 2 = 74
- 74 / 2 = 37
- 37 / 2 = 18
- 18 / 2 = 9
- 9 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
Представьте, что в алгоритме, где линейный поиск идёт по всем элементам массива в 10 миллиардов данных и проверка каждого элемента занимает 1 секунду, общее время работы составит 317 лет. В то время как двоичный поиск выполнит лишь 32 проверки, что займёт 32 секунды!
Такова разница между сложностью и .
Задание
Дан список из
n оценок в диапазоне от 1 до 4 (где 1 — это самая низкая оценка, а 4 — наивысшая), а также несколько пороговых значений. Нужно определить, сколько человек продолжат обучение в следующем классе, если для прохождения требуется оценка не ниже заданного порога.Ввод
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ ) — количество учеников.В следующей строке содержится
n чисел с плавающей точкой — оценки учеников, упорядоченные по возрастанию (1 ≤ ≤ 4).Третья строка содержит одно целое число
q (1 ≤ q ≤ ) — количество пороговых значений.В последней строке даны
q чисел с плавающей точкой — минимальные пороги для прохождения (1 ≤ ≤ 4).Вывод
Программа должна вывести
q строк. Строка i должна содержать количество учеников, которые смогут перейти в следующий класс при пороге .Примеры
Ввод | Вывод |
10
1.1 1.2 1.4 1.7 2 3 3.3 3.5 3.8 3.8
5
3.7
3.8
1
1.5
2 | 2
2
10
7
6 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB