2020 - Týždeň 4

Zhrnutie prednášky

Štvrtý týždeň semestra prebieha dištančne, pričom lektor upozorňuje na blížiaci sa termín zadania a odporúča objednať si Arduino kity. Prednáška nadväzuje na štruktúry z minulého týždňa (štruktúra Person so serializáciou a deserializáciou) a venuje sa vyhľadávaniu v poli štruktúr. Lineárne vyhľadávanie sa upraví na hľadanie podľa veku (celé číslo) aj podľa priezviska pomocou funkcie strcmp, pričom vráti index prvej nájdenej položky alebo -1. Následne sa predstavuje binárne vyhľadávanie (funkcia bsearch zo stdlib.h), ktoré vyžaduje zoradený zoznam a opakovane delí interval na polovicu. Porovnáva sa zložitosť: lineárne vyhľadávanie je O(n), binárne logaritmické.

• - Lineárne vyhľadávanie prechádza pole po prvku a vracia index prvej zhody alebo -1.
• - Pri poli štruktúr sa hľadá podľa konkrétnej položky cez operátor bodka (napr. vek).
• - Vyhľadávanie podľa reťazca (priezvisko) využíva strcmp zo string.h; zhoda je pri výsledku 0.
• - Lineárne vyhľadávanie nájde len prvú zhodu, takže ďalšie osoby s rovnakým vekom sa neobjavia.
• - Binárne vyhľadávanie vyžaduje zoznam zoradený podľa hľadanej položky a delí interval na polovicu.
• - Knižnica stdlib.h ponúka hotovú funkciu bsearch, ktorú je vhodnejšie použiť než vlastnú implementáciu.
• - Zložitosť lineárneho vyhľadávania je O(n), binárneho logaritmická, čo je pri veľkých poliach zásadný rozdiel.

Zhrnutie pripravené s pomocou AI z prepisu videa.