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 listi
Traženje redom
Binarno pretraživanje
100
do 100 koraka
do 7 koraka
100 000
do 100 000 koraka
do 17 koraka
1 000 000 000
do milijardu koraka
do 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) - 1while lo <= hi:
mid = (lo + hi) // 2if a[mid] == x:
return mid
elif a[mid] < x:
lo = mid + 1else:
hi = mid - 1return -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) // 2if a[mid] < x:
lo = mid + 1else:
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) // 2if mid * mid <= n:
lo = mid
else:
hi = mid - 1print(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?
Svako pitanje prepolovi interval: 2^10 = 1024.
Pitanje
Što mora vrijediti za binarno pretraživanje u listi?
Samo u sortiranoj listi možemo odbaciti pola.
Pitanje
Što je „pretraživanje po odgovoru”?
Ako uvjet za neki odgovor vrijedi, vrijedi i za sve veće.
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.
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.