Перед самим Новим Роком дід Мороз вирішив знайти собі помічничку-Снігурку. Дідусь був трохи дивний – він боявся високих снігурок, але малі йому не подобались. Тому він шукав або таку, яка одного з ним зросту, або трошки меншу.
Дід Мороз прийшов на спеціальні курси і побачив там одночасно стоп’ятсот снігурок. Можна було, звичайно, мірятися зростом з кожною з них, але так можна було шукати до травня. Але дід був програмістом на Python і тому попросив снігурок вишукуватися в шеренгу, як на уроці фізкультури – відсортованими по зросту, від самої малої до самої високої.
Він поділив цю шеренгу навпіл, підійшов до снігурки, що була посередині і помірявся з нею зростом. Снігурка була вища зростом за діда Мороза. Це означало, що серед другої, високої половини снігурок йому пари немає, він їх всіх боїться, тому високу половину можна з пошуків виключити. Половину, що залишилась, він знову поділив на дві частини, підійшов до снігурки, що була посередині і помірявся з нею зростом. Ну і так далі до тих пір, поки не знайшов саме ту Снігурку, що шукав.
Подібний алгоритм пошуку, з поділом сортованого списку на дві частини зветься бінарним або двійковим пошуком. Це відомий і швидкий алгоритм.
І не просто так дід Мороз був програмістом на Python. Річ у тому, що в Python бінарний пошук вже є. Він реалізований в стандартній бібліотеці. Потрібні діду Морозу функції знаходяться в модулі bisect.
Якщо б всі снігурки були б різного зросту, то ось як просто діду Морозу знайти свою:
import bisect
did_moroz = 180
snigurky = [151, 160, 163, 171, 175, 180, 183, 200]
moya = bisect.bisect_left(snigurky, did_moroz)
print(moya)
Результат: 5 (п’ята в черзі, черга нумерується від нуля)
Якщо точно такої за зростом немає, то можна знайти найближчу меншу:
import bisect
did_moroz = 174
snigurky = [151, 160, 163, 171, 175, 180, 183, 200]
moya = bisect.bisect_left(snigurky, did_moroz)
print(moya)
Результат: 4 (четверта в черзі, черга нумерується від нуля, це снігурка зі зростом 171)
А якщо зріст снігурок може дублюватися і діду Морозу підходить не одна, а кілька снігурок? Давайте ми йому в такому випадку скажемо кількість снігурок, що йому підходять, нехай сам з тим розбирається:
import bisect
did_moroz = 180
snigurky = [151, 160, 163, 171, 175, 180, 180, 180, 200]
moya_mensha = bisect.bisect_left(snigurky, did_moroz)
moya_bilsha = bisect.bisect_right(snigurky, did_moroz)
print(moya_bilsha - moya_mensha)
Результат: 3 (діду Морозу підходять три снігурки однакового зросту)
Ось так просто і стильно це все в Python.
Давайте використаємо бінарний пошук для розв’язання задачі 3970 з e-olymp – з назвою МУТАНТИ.
Умова:
Вже тривалий час в Інституті Местецтв, Мутантів та Інформаційоних Технологій розводять милих різнокольорових звіряток. Для зручності кожний колір позначено своїм номером, усього кольорів не більше 109. В один з прекрасних днів у розпліднику сталося диво: усі тваринки вишикувалися в ряд в порядку зростання кольорів. Користуючись нагодою, лаборанти вирішили порахувати, скільки звіряток різних кольорів живе у розпліднику, і, за законом жанру, попросили вас написати програму, яка допоможе їм у вирішенні цього нелегкого завдання.
Вхідні дані
У першому рядку вхідного файлу міститься єдине число N (0 ≤ N ≤ 105) - кількість звіряток в Інституті. У наступному рядку знаходиться N упорядкованих за неспаданням невід'ємних цілих чисел, які не перевищують 109 і відокремлених пропусками - їх кольори. У третьому рядку файлу записано число M (1 ≤ M≤ 100000) - кількість запитів вашій програмі, у наступному рядку через пропуск записано M цілих невід'ємних чисел (які не перевищують 109+1).
Вихідні дані
Вихідний файл повинен містити M рядків. Для кожного запиту виведіть кількість звіряток заданого кольору у розпліднику.
Ліміт часу 4 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
10
1 1 3 3 5 7 9 18 18 57
5
57 3 9 1 179
Вихідні дані #1
1
2
1
2
0
Можна підряд перебирати список і шукати потрібні елементи. Але при такому підході ми не встигнемо розв’язати задачу за відведений час. Тому, розуміючи, що бінарний пошук – чудова по оптимальності штука, давайте використаємо саме його. Думаю, після допомоги діду Морозу в його пошуку Снігурок, лістинг програми «Мутанти» не потребує пояснень:
from bisect import bisect_left, bisect_right
n = int(input())
colors = [int(x) for x in input().split()]
m = int(input())
request = [int(x) for x in input().split()]
for i in range(m):
find_left = bisect_left (colors, request[i])
find_right = bisect_right(colors, request[i])
print (find_right - find_left)