Двоично търсене

Код на:JavaC#PythonJavaScript

Накратко: Двоичното търсене намира стойност в подреден масив, като сравнява със средата и всеки път изхвърля половината: O(log n) сравнения.

Проблем

Филтърът, който чете целия каталог

Магазинът има 1 000 000 продукта, а ценоразписът е подреден по цена. Филтърът „точна цена“ търси с цикъл от началото, като линейното търсене. Цените в кода са в евроцентове: от 2 до 2 000 000. Клиент търси продукт за 20 000,01 €, а такъв няма:

n = 1_000_000
prices = [2 * (i + 1) for i in range(n)]
target = 2 * n + 1

comparisons = 0
found = -1
for i in range(n):
    comparisons += 1
    if prices[i] == target:
        found = i
        break
print(f"Индекс: {found}")
print(f"Сравнения: {comparisons}")

Изход

Индекс: -1
Сравнения: 1000000

Милион сравнения, за да кажеш „няма“. А при всяко отваряне на страницата филтърът се пуска за десетки цени.

Цените са подредени, а цикълът не се възползва от това. Когато търсиш дума в речник, не четеш от първата страница. Отваряш по средата и гледаш дали думата е преди или след.

Идеята

Питай средата, изхвърли половината

Погледни цената по средата на ценоразписа:

• ако е търсената, готово;
• ако е по-малка, търсената може да е само вдясно. Лявата половина отпада, заедно със средата;
• ако е по-голяма, търсената може да е само вляво.

После същото с половината, която остава. Това е двоично търсене (binary search). Обхватът, в който цената още може да е, се пази с два индекса: lo (началото) и hi (краят). Средата е mid.

Всяко сравнение разполовява обхвата. 1 000 000 цени стават 500 000, после 250 000, и след около 20 деления остава една. Колко пъти делиш на 2, докато стигнеш до 1, се казва логаритъм при основа 2: log₂ 1 000 000 ≈ 20. Затова двоичното търсене е O(log n), а линейното е O(n).

Условието е едно: масивът трябва да е подреден. В неподреден масив „по-малка е, значи е вдясно“ не е вярно.

Виж го

lo, mid и hi в ценоразписа

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]
print(f"Индекс: {find(prices, 49)}")

Изход

Индекс: 12

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Стъпка по стъпка, с думи

1. Ценоразписът е подреден: 15 цени. Търсим 49 €. lo и hi обхващат всичко, от 0 до 14.
2. mid = 7: 27 € < 49 €, значи цената е вдясно. lo = 8, лявата част отпада. Остават 7 цени.
3. mid = 11: 44 € < 49 €, значи цената е вдясно. lo = 12, лявата част отпада. Остават 3 цени.
4. mid = 13: 53 € > 49 €, значи цената е вляво. hi = 12, дясната част отпада. Остава 1 цена.
5. mid = 12: 49 €. Това е търсената цена: find връща 12.
6. 4 сравнения. Търсене от началото би погледнало 13 цени, а за 1 000 000 цени двоичното търсене иска най-много 20.

Средата е (lo + hi) // 2: // дели и закръгля надолу до цяло число. В Java и C# се пише по друг начин, защото там сборът може да прелее. В Python не може: на една от следващите карти е защо.

По-точно, за любопитните

Най-лошият случай е, когато цената я няма: обхватът се дели, докато lo не мине hi. За n цени това са най-много ⌊log₂ n⌋ + 1 сравнения: 4 за 10 цени, 10 за 1000, 20 за 1 000 000. Най-добрият случай е едно сравнение: цената е точно на средата.

Тук „сравнение“ е една проба на mid. Проверката за равно и за по-малко са два реда в кода, но питат за една и съща цена.

Пробвай

Предвиди колко проби

Подредени цени в евроцентове: 2, 4, 6, …, 2000. Търси се 2001, а такава цена няма. Колко пъти минава цикълът?

n = 1000
prices = [2 * (i + 1) for i in range(n)]
target = 2 * n + 1

steps = 0
lo = 0
hi = n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    steps += 1
    if prices[mid] == target:
        break
    elif prices[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(steps)

Отговор

10

500

1000

Провери

Пробвай

Попълни

Цената на mid е по-малка от търсената. Откъде започва новият обхват?

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = 
        else:
            hi = mid - 1
    return -1

Провери

Идеята

Границите: къде греши всеки

Двоичното търсене се пише в шест реда, а е известно с това, че се пише грешно. Грешката почти винаги е с едно: < вместо <=, mid вместо mid - 1. Казва се off-by-one (грешка с единица).

Пазиш я с едно решение: какво значат lo и hi, и после го спазваш навсякъде.

• Затворен обхват [lo, hi]: и двата края може да са цената. hi започва от последния индекс, цикълът е докато lo <= hi, а изхвърлената среда е hi = mid - 1 и lo = mid + 1. Това е find от горе.
• Полуотворен обхват [lo, hi): hi е първото място след обхвата. hi започва от дължината на масива, цикълът е докато lo < hi, а наляво се отива с hi = mid, защото hi така и така не е в обхвата.

Двете са верни. Грешката е, когато ги смесиш. Ето затворен обхват с hi = mid от полуотворения. Търси се 4 €, а такава цена няма. Ограничителят спира цикъла след 8 проби, иначе нямаше да спре:

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    probes = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        print(f"lo={lo} hi={hi} mid={mid}")
        probes += 1
        if probes == 8:
            print("Спирам след 8 проби: lo и hi не мърдат")
            return -1
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]
find(prices, 4)

Изход

lo=0 hi=14 mid=7
lo=0 hi=7 mid=3
lo=0 hi=3 mid=1
lo=0 hi=1 mid=0
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
Спирам след 8 проби: lo и hi не мърдат

Когато lo и hi станат 1, средата е 1, цената там е 5 €, повече от 4 €, и hi = mid пак е 1. Нищо не се сменя. Това е безкраен цикъл: програмата не пада, само виси.

Пробвай

Намери грешката

Търсенето намира 49 €, но не намира най-скъпия продукт, 58 €, макар че той е в ценоразписа:

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]
print(f"Индекс: {find(prices, 58)}")

Изход

Индекс: -1

Избери реда с грешката.

1def find(prices, target):2 lo = 03 hi = len(prices) - 14 while lo < hi:5 mid = (lo + hi) // 26 if prices[mid] == target:7 return mid8 elif prices[mid] < target:9 lo = mid + 110 else:11 hi = mid - 112 return -1

Провери

Идеята

Когато (lo + hi) / 2 прелива

В Java и C# int стига до 2 147 483 647, и при масив с повече от милиард елемента (lo + hi) / 2 прелива: сборът става отрицателно число. Затова там средата се пише lo + (hi - lo) / 2.

В Python целите числа нямат горна граница. Сборът е по-голямо число и толкова:

lo = 1_500_000_000
hi = 2_000_000_000
print((lo + hi) // 2)
print(lo + (hi - lo) // 2)

Изход

1750000000
1750000000

(lo + hi) // 2 е вярно при всякакъв размер. lo + (hi - lo) // 2 също работи, но тук не пази от нищо.

По-точно, за любопитните

Грешката не е измислена. Двоичното търсене в стандартната библиотека на Java, Arrays.binarySearch, е имало (low + high) / 2 девет години. Джошуа Блох го описва през 2006 г. в статията „Nearly All Binary Searches and Mergesorts are Broken“: програма с масив от повече от 2³⁰ елемента пада с ArrayIndexOutOfBoundsException. Днес там пише (low + high) >>> 1.

Виж го

Първата цена от 20 € нагоре

Филтърът „цена от 20 €“ не търси точна цена. Търси първото място, където цената е поне 20 €: от него нататък са всички продукти, които трябва да покаже. Това се казва долна граница (lower bound). Тя е и първото срещане: ако цените имат три продукта по 15 €, долната граница на 15 е първият от тях.

find не я дава: той спира на първото 15, на което стъпи. Долната граница е с полуотворен обхват, и цикълът не спира при равно, а продължава наляво:

def lower_bound(prices, target):
    lo = 0
    hi = len(prices)
    while lo < hi:
        mid = (lo + hi) // 2
        if prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49]
print(f"find: {find(prices, 15)}")
first = lower_bound(prices, 15)
print(f"Първото 15 €: индекс {first}")
print(f"Продукти по 15 €: {lower_bound(prices, 16) - first}")
from20 = lower_bound(prices, 20)
print(f"Първата цена от 20 € нагоре: {prices[from20]} €")

Изход

find: 5
Първото 15 €: индекс 4
Продукти по 15 €: 3
Първата цена от 20 € нагоре: 24 €

Ако цената е по-малка от търсената, тя и всичко преди нея отпадат: lo = mid + 1. Иначе mid може да е отговорът, затова остава в обхвата: hi = mid. Цикълът свършва, когато lo и hi се срещнат, а там е първото място с цена ≥ търсената. Ако такова няма, lo е дължината на масива. Колко продукта са по 15 €, е разликата между две долни граници: на 16 и на 15.

В Python долната граница е готова: модулът bisect. bisect_left е точно lower_bound от горе, а bisect_right дава първото място с цена, по-голяма от търсената:

import bisect

prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49]
print(bisect.bisect_left(prices, 24))
print(bisect.bisect_left(prices, 20))
print(bisect.bisect_left(prices, 15))
print(bisect.bisect_right(prices, 15))

Изход

8
8
4
7

bisect_right(prices, 15) - bisect_left(prices, 15) е колко продукта са по 15 €. Дали точната цена я има, проверяваш така: i < len(prices) and prices[i] == x. bisect.insort слага нов елемент на мястото му в подреден списък.

Виж го

Измери: линейно срещу двоично

Линейното и двоичното търсене в същия подреден ценоразпис, когато търсената цена я няма. Линейното сравнява всяка цена: n сравнения. Двоичното прави 20 сравнения при 1 000 000 цени:

• Линейно търсене (всяка цена) O(n)
• Двоично търсене O(log n)

Алгоритъм	n = 10	n = 1000	n = 100 000	n = 1 000 000
Линейно търсене (всяка цена)	10	1000	100 000	1 000 000
Двоично търсене	4	10	17	20

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Кривата на двоичното почти лежи: при 100 пъти повече цени тя се качва с около 7 сравнения. Затова двоичното търсене е навсякъде, където нещо е подредено: индексите в базите данни, git bisect, търсенето на версия, от която тестът пада.

Упражнение

Ценовият филтър: от 10 € до 30 €

Реши задачата в редактора си.

От 10 € до 30 €. Филтърът показва колко продукта има с цена от 10 € до 30 € включително. Ценоразписът е подреден: 3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 и 49 €. Не обхождай целия масив: с две двоични търсения намери първото място с цена ≥ 10 € и първото с цена ≥ 31 €. Разликата е броят.

Изход

От 10 € до 30 €: 7 продукта

Още задачи

• Последното срещане. Напиши upper_bound: първото място с цена, по-голяма от търсената. Последният продукт по 15 € е на едно място преди него.
• Свободен час за доставка. Свободните часове за доставка са подреден масив от минути от полунощ (540 е 9:00). Клиентът иска доставка не по-рано от 14:10. Намери първия свободен час или кажи, че няма.
• Къде влиза новата цена. Нов продукт за 21 € трябва да влезе в ценоразписа, без той да спре да е подреден. Намери мястото с двоично търсене.

Тест

Провери се

1. Ценоразписът има 1 000 000 цени, подредени по големина. Най-много колко сравнения прави двоичното търсене?

201000500 000

2. Обхватът е затворен: hi започва от последния индекс. Кое условие на цикъла е вярно?

lo <= hilo < hilo != hi

3. При while (lo <= hi) някой пише hi = mid вместо hi = mid - 1. Какво става?

Когато lo и hi се срещнат, а цената на mid е по-голяма, hi остава същото и цикълът не спираНищо, търсенето е само малко по-бавноПрограмата не се компилира

4. Цените имат три продукта по 15 €. Кой търсиш, за да покажеш всички продукти „от 15 € нагоре“?

Което и да е 15, което двоичното търсене намериПоследното 15 €Първото място с цена ≥ 15 € (долната граница)

5. Списъкът с продукти не е подреден. Става ли двоично търсене?

Не: отговорът е грешен, защото половината, която изхвърляш, може да съдържа ценатаДа, само е по-бавноДа, ако списъкът е малък

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Времева сложност: броене на стъпки · Big-O: как расте работата · Най-добър, среден и най-лош случай · Линейно търсене
• Продължава в: Двоично търсене по отговора · Бързо степенуване · Разделяй и владей и дървото на рекурсията · Двоично дърво за търсене
• Задачи по темата: Търсене