nechodím na prednáškyADŠ prednáška 08: Binárne vyhľadávanie. Binárne vyhľadávacie stromy.
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška sa venuje binárnemu vyhľadávaniu v usporiadanom poli a jeho robustnej implementácii bez chýb s off-by-one indexmi. Vysvetľuje sa myšlienka delenia poľa na stred a zahadzovania polovice podľa porovnania s hľadanou hodnotou x. Kľúčovou technikou je práca s invariantom, kde sa prvky poľa rozdeľujú na 'dobré' a 'zlé' a hľadá sa hranica medzi nimi pomocou dvoch pomocných indexov (ľavého a pravého 'prsta') umiestnených symbolicky mimo poľa. Tento prístup eliminuje špeciálne okrajové prípady a umožňuje napísať algoritmus bez plus-mínus jednotkových chýb. Následne sa zavádza koncept polootvorených intervalov, ktoré majú výhodné vlastnosti pri reprezentácii rozsahov, ich delení a reprezentácii prázdnej množiny.
- - Binárne vyhľadávanie hľadá prvok v usporiadanom poli delením na polovice v čase O(log n).
- - Ide o algoritmus, pri ktorom sa historicky robí najviac implementačných chýb typu off-by-one.
- - Riešením je preformulovať úlohu ako hľadanie hranice medzi 'dobrými' a 'zlými' prvkami.
- - Používajú sa symbolické indexy mimo hraníc poľa (ľavý prst na dobrom, pravý na zlom prvku).
- - Invariant algoritmu: ľavý index vždy ukazuje na dobrý prvok, pravý na zlý prvok.
- - Implementácia bez okrajových prípadov a bez rizika pretečenia pri výpočte stredu.
- - Zavádza sa koncept polootvorených intervalov [x, y) s výhodnými vlastnosťami pre delenie a prázdnu množinu.
Zhrnutie pripravené s pomocou AI z prepisu videa.
