Python stazaCjelina 4 · Prvi algoritmiLekcija 27

Binarno pretraživanje (binary search)

Kako u sortiranoj listi od milijun brojeva naći traženi u samo 20 koraka? Isto kao u igri pogađanja: pitaj za sredinu i izbaci pola.

Pythonoko 45 minuta4 zadatka za evaluator

1Igra pogađanja

Sjeti se igre iz lekcije 25: zamislio sam broj od 1 do 100, a ti smiješ pitati samo „je li veći od…?“. Najbolje je svaki put pitati za sredinu. Svaki odgovor izbaci polovicu mogućnosti, pa ti treba najviše 7 pitanja.

Isto vrijedi za traženje u sortiranoj listi. Pogledaj srednji element. Ako je traženi broj veći, sigurno nije u lijevoj polovici; ako je manji, nije u desnoj. Tako svakim korakom prepolovimo dio liste u kojem tražimo. To je binarno pretraživanje (engl. binary search).

Elemenata u listiTraženje redomBinarno pretraživanje
100do 100 korakado 7 koraka
100 000do 100 000 korakado 17 koraka
1 000 000 000do milijardu korakado 30 koraka

2Kako radi

Pamtimo granice dijela liste u kojem još tražimo: lijevu lo i desnu hi. Dok taj dio nije prazan, gledamo srednji element i prepolovimo dio.

lo–
hi–
mid–
nadeno–
Klikni „Sljedeći korak“ i prati što se događa.
Ključna ideja

Za 10 elemenata trebala su samo 3 koraka. Traženjem redom trebalo bi 6.

Pazi

Binarno pretraživanje radi samo na sortiranoj listi. Ako lista nije sortirana, prvo je sortiraj, kao u lekciji 19.

3Kao funkcija

Binarno pretraživanje je zgodno spremiti u funkciju, da ga možemo pozvati za mnogo pitanja.

def trazi(a, x):
    lo = 0
    hi = len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
Pazi

Granice se pomiču na mid + 1 i mid - 1, a ne na mid. Inače se dio liste ne bi uvijek smanjio i petlja se ne bi zaustavila.

4Koliko je manjih od x

Česta varijanta: koliko je elemenata sortirane liste manje od x? To je isto što i indeks prvog elementa koji je veći ili jednak x. Tražimo granicu između „manjih“ i „ostalih“.

Program
def manjih_od(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [2, 5, 8, 12, 16, 23]
print(manjih_od(a, 12))
print(manjih_od(a, 13))
print(manjih_od(a, 100))
Ispis
3 4 6
Ključna ideja

Ovdje je hi = len(a), a petlja ide dok je lo < hi. Na kraju su lo i hi jednaki i pokazuju točno na granicu.

5Pretraživanje po odgovoru

Binarno pretraživanje ne treba nužno listu. Treba nam samo pitanje na koje je odgovor „ne, ne, ne, …, da, da, da“. Primjer: najveći cijeli broj k za koji je k · k ≤ N. Za mali k odgovor je „da“, a od nekog k nadalje „ne“. Tu granicu tražimo prepolovljavanjem.

n = int(input())
lo = 0
hi = n
while lo < hi:
    mid = (lo + hi + 1) // 2
    if mid * mid <= n:
        lo = mid
    else:
        hi = mid - 1
print(lo)
Ulaz
1000000000000000000
Ispis
1000000000
Ključna ideja

Za N do 10¹⁸ trebalo bi oko 60 koraka. Petljom koja isprobava k = 1, 2, 3… trebala bi milijarda koraka.

Pazi

Ovdje je sredina (lo + hi + 1) // 2. Kad bi bila (lo + hi) // 2, za lo = 0 i hi = 1 sredina bi bila 0, lo bi ostao 0 i petlja se ne bi zaustavila.

6Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Na koliko se pitanja najviše pogodi broj od 1 do 1000 binarnim pretraživanjem?

Pitanje

Što mora vrijediti za binarno pretraživanje u listi?

Pitanje

Što je „pretraživanje po odgovoru”?

7Zadaci

Gdje je

★☆☆ lagano

Zadana je sortirana lista različitih brojeva i broj x. Na kojem je mjestu x? Mjesta su numerirana od 1.

Ulaz
U prvom retku N i x. U drugom retku N različitih brojeva, poredanih od najmanjeg.
Izlaz
Mjesto broja x ili -1 ako ga nema.
Ograničenja
1 ≤ N ≤ 100 000
Ulaz
6 16 2 5 8 12 16 23
Izlaz
5
Ulaz
3 4 1 2 3
Izlaz
-1
Riješi u evaluatoru

Koliko ih je do x

★★☆ srednje

Zadana je lista od N brojeva i Q pitanja. Za svako pitanje x ispiši koliko je brojeva u listi manje ili jednako x.

Ulaz
U prvom retku N, u drugom N brojeva. U trećem retku Q, u četvrtom Q brojeva x.
Izlaz
Q redaka s odgovorima.
Ograničenja
1 ≤ N, Q ≤ 100 000, brojevi su od 1 do 1 000 000 000
Ulaz
5 7 2 9 2 5 4 2 6 1 9
Izlaz
2 3 0 5
Treba ti pomoć?

Sortiraj listu jednom. Za svako pitanje binarnim pretraživanjem nađi granicu kao u dijelu 4, samo s uvjetom ≤ umjesto <.

Riješi u evaluatoru

Cijeli korijen

★★☆ srednje

Koji je najveći cijeli broj k za koji je k · k ≤ N?

Ulaz
Jedan prirodni broj N.
Izlaz
Traženi k.
Ograničenja
1 ≤ N ≤ 10¹⁸
Ulaz
50
Izlaz
7
Ulaz
49
Izlaz
7
Treba ti pomoć?

Pretraživanje po odgovoru iz dijela 5.

Riješi u evaluatoru

Džeparac

★★★ teže

U trgovini je N igračaka sa zadanim cijenama. Q djece dolazi s različitim iznosima džeparca. Za svako dijete ispiši koliko najviše različitih igračaka može kupiti.

Ulaz
U prvom retku N, u drugom N cijena. U trećem retku Q, u četvrtom Q iznosa džeparca.
Izlaz
Q redaka s odgovorima.
Ograničenja
1 ≤ N, Q ≤ 100 000, cijene su od 1 do 10 000, džeparci od 1 do 1 000 000 000
Ulaz
5 7 3 10 2 4 3 1 9 100
Izlaz
0 3 5
Treba ti pomoć?

Najviše igračaka kupuje se uzimanjem najjeftinijih. Sortiraj cijene i napravi prefiksne zbrojeve iz lekcije 26: p[k] je cijena k najjeftinijih. Za svako dijete binarnim pretraživanjem nađi najveći k za koji je p[k] ≤ džeparac.

Riješi u evaluatoru

8Što smo naučili

  • Binarno pretraživanje radi na sortiranoj listi i svakim korakom prepolovi dio u kojem tražimo: O(log N).
  • Pamtimo granice lo i hi; gledamo sredinu mid = (lo + hi) // 2.
  • Granice pomičemo na mid + 1 ili mid − 1, inače se petlja može vrtjeti zauvijek.
  • Varijanta „koliko je manjih od x“ traži granicu između dvije skupine.
  • Pretraživati se može i po odgovoru, kad je odgovor „ne, ne, …, da, da“.
Najčešće greške

Nesortirana lista · granica na mid umjesto mid ± 1 · beskonačna petlja zbog krive sredine · zamijenjeni < i ≤