Cieľ cvičenia

V súbore binary_search.py implementujte funkciu:

def find(search_list, value):
    ...

Funkcia má v zoradenom zozname search_list nájsť hodnotu value a vrátiť jej index. Ak sa hodnota v zozname nenachádza, musí vyvolať výnimku:

raise ValueError("value not in array")

Testy kontrolujú aj presné znenie chybovej správy.

Čo je binárne vyhľadávanie?

Binárne vyhľadávanie hľadá hodnotu tak, že opakovane rozdeľuje interval možných pozícií na polovice. Pri každom kroku porovná hľadanú hodnotu so stredným prvkom:

1. Ak sa hodnoty rovnajú, vrátime index stredného prvku.
2. Ak je stredný prvok väčší než hľadaná hodnota, hľadáme v ľavej polovici.
3. Ak je stredný prvok menší než hľadaná hodnota, hľadáme v pravej polovici.
4. Ak už žiadna pozícia nezostala, hodnota sa v zozname nenachádza.

Algoritmus funguje iba vtedy, keď je zoznam zoradený vzostupne. Vďaka tomu môžeme po každom porovnaní bezpečne vylúčiť polovicu kandidátov.

Pri n prvkoch potrebuje binárne vyhľadávanie najviac približne log₂(n) krokov, teda má časovú zložitosť O(log n). Obyčajné prehľadávanie od začiatku by v najhoršom prípade potrebovalo O(n) krokov.

Príklad

Hľadajme číslo 23 v zozname:

[4, 8, 12, 16, 23, 28, 32]

• Stredný prvok je 16. Keďže 23 je väčšie, ľavú časť môžeme vylúčiť.
• Zostane úsek [23, 28, 32]. Jeho stredný prvok je 28.
• Keďže 23 je menšie než 28, ponecháme ľavú časť.
• Zostane hodnota 23, ktorú nájdeme na indexe 4 v pôvodnom zozname.

Pri implementácii nepracujte iba s novými podzoznamami. Efektívnejšie je uchovávať hranice aktuálneho úseku:

low = 0
high = len(search_list) - 1

Stred vypočítate pomocou celočíselného delenia:

middle = (low + high) // 2

Ak je search_list[middle] príliš veľké, nastavte:

high = middle - 1

Ak je príliš malé, nastavte:

low = middle + 1

Posun o 1 je dôležitý: stredný prvok už bol skontrolovaný, preto ho pri ďalšom hľadaní netreba ponechať v intervale.

Odporúčaný postup

1. Nastavte low na index prvého prvku a high na index posledného prvku.
2. Opakujte hľadanie, kým platí low <= high.
3. Vypočítajte middle a porovnajte search_list[middle] s value.
4. Pri zhode okamžite vráťte middle.
5. Podľa porovnania zúžte interval na ľavú alebo pravú polovicu.
6. Ak cyklus skončí bez návratu indexu, vyvolajte ValueError s požadovanou správou.

Podmienka low <= high pokrýva aj interval s jedinou zostávajúcou pozíciou. Keď sa hranice prekročia, všetky možné pozície boli vylúčené. Takto sa správne spracuje aj prázdny zoznam.

Časté chyby

• Zabudnutie, že index posledného prvku je len(search_list) - 1, nie len(search_list).
• Použitie low < high, čím sa môže vynechať posledný možný prvok.
• Nastavenie hranice na middle namiesto middle - 1 alebo middle + 1, čo môže spôsobiť nekonečný cyklus.
• Vrátenie hodnoty namiesto jej indexu.
• Použitie lineárneho prehľadávania namiesto binárneho vyhľadávania.
• Vyvolanie nesprávneho typu výnimky alebo nesprávnej správy.

Užitočné odkazy na Python manuál

• len() – Built-in Functions
• Celočíselné delenie // – Binary arithmetic operations
• Indexovanie a subscription
• while statement
• raise statement
• ValueError – Built-in Exceptions

Kontrola pred odovzdaním

• Funkcia vracia správny index pre prvý, stredný aj posledný prvok.
• Funguje pre zoznam s párnym aj nepárnym počtom prvkov.
• Správne funguje pre jednoprvkový aj prázdny zoznam.
• Pri nenájdenej hodnote vyvolá ValueError("value not in array").
• Hranice sa po každom kroku skutočne zmenšia.
• Zoznam sa počas vyhľadávania nemení.

Previous Post Next Post