Binary Search – binárne vyhľadávanie
Čo sa v cvičení naučíte
Po vyriešení cvičenia budete vedieť:
- vysvetliť princíp binárneho vyhľadávania,
- vyhľadávať hodnotu v zoradenom zozname delením priestoru na polovice,
- pracovať s ľavým a pravým okrajom časti zoznamu,
- vypočítať index stredného prvku,
- používať cyklus
whilena opakovanie hľadania, - rozlíšiť nájdenú hodnotu od situácie, keď sa hodnota v zozname nenachádza,
- vyvolať vhodnú výnimku pomocou
raise ValueError(...), - porovnať efektívnosť binárneho vyhľadávania s postupným prehľadávaním zoznamu.
Čo si musíte preštudovať
Pred riešením si zopakujte najmä tieto témy:
Zoznamy, indexy a dĺžka zoznamu
Vstupom je zoznam čísel, napríklad:
numbers = [4, 8, 12, 16, 23, 28, 32]Indexovanie začína od nuly. Prvý prvok je teda numbers[0] a posledný prvok má index len(numbers) - 1. Binárne vyhľadávanie pracuje s indexmi, nie priamo s pozíciami typu „prvý“ alebo „posledný“.
Preštudujte si:
- Zoznamy v referenčnej príručke Pythonu,
- Prístup k prvkom pomocou indexov a rezanie zoznamov,
- vstavanú funkciu
len().
Porovnávanie hodnôt
Pri každom kroku porovnáte hľadanú hodnotu so stredným prvkom:
- ak sú rovnaké, hľadanie je úspešné,
- ak je hľadaná hodnota menšia, pokračujete v ľavej polovici,
- ak je hľadaná hodnota väčšia, pokračujete v pravej polovici.
Zopakujte si relačné operátory <, > a == a logiku podmienok if/elif/else v tutoriáli Pythonu.
Cyklus while
Rozsah možných indexov sa bude postupne zmenšovať. Kým ešte existuje neprázdna časť zoznamu, cyklus vypočíta jej stred a vykoná ďalšie porovnanie.
Preštudujte si syntax a podmienku cyklu
while
a dávajte pozor, aby sa v každej iterácii zmenil ľavý alebo pravý okraj. Inak môže program skončiť v nekonečnom cykle.
Celé delenie
Index stredu musí byť celé číslo. Na jeho výpočet použijete celé delenie //, napríklad:
middle = (left + right) // 2Rozdiel medzi obyčajným delením / a celým delením // vysvetľuje dokumentácia k aritmetickým operáciám.
Výnimky a ValueError
Podľa zadania sa pri nenájdení hodnoty nemá vracať špeciálny index, napríklad -1. Funkcia má vyvolať výnimku typu ValueError a pripojiť k nej správu:
raise ValueError("value not in array")Preštudujte si vyvolávanie výnimiek pomocou raise a štandardné typy výnimiek. Testy kontrolujú nielen typ výnimky, ale aj to, že obsahuje správu.
Ako postupovať pri riešení
- Prečítajte si zadanie na Exercism – Binary Search a pozrite si pripravenú funkciu a testy.
- Nastavte ľavý okraj na index prvého prvku a pravý okraj na index posledného prvku.
- Kým je ľavý okraj menší alebo rovný pravému, vypočítajte index stredu.
- Porovnajte prvok na strednom indexe s hľadanou hodnotou.
- Ak ste hodnotu našli, vráťte jej index.
- Ak je stredný prvok príliš veľký, posuňte pravý okraj pred stred. Ak je príliš malý, posuňte ľavý okraj za stred.
- Ak sa cyklus skončí bez úspechu, vyvolajte
ValueErrors požadovanou správou.
Pri riešení si nakreslite napríklad zoznam [4, 8, 12, 16, 23, 28, 32] a sledujte, ako sa pri hľadaní čísla 23 menia hodnoty left, middle a right.
Na čo si dať pozor
- Binárne vyhľadávanie funguje iba v zoradenom zozname. Zoznam v tomto cvičení už zoradený je — vo funkcii ho nemusíte znova triediť.
- Pri posúvaní hranice treba vylúčiť aj už skontrolovaný stredný prvok; inak môže cyklus opakovať rovnaký krok.
- Prázdny zoznam musí skončiť vyvolaním
ValueError. - Otestujte prvý a posledný prvok, hodnotu menšiu než všetky prvky, väčšiu než všetky prvky aj hodnotu, ktorá v zozname nie je.
Prečo je algoritmus rýchly
Postupné vyhľadávanie môže v najhoršom prípade skontrolovať každý prvok, takže má časovú zložitosť O(n). Binárne vyhľadávanie pri každom kroku zahodí približne polovicu možností, preto má časovú zložitosť O(log n). Udržiavanie hraníc však vyžaduje konštantnú dodatočnú pamäť O(1).
Ďalšie informácie o efektívnosti operácií so zoznamami nájdete v prehľade Time Complexity of Python Operations.