Lineárne vs. binárne vyhľadávanie
Lineárne vs. binárne vyhľadávanie je interaktívny pokus z aplikácie Algoritmy v akcii, bezplatnej simulácie zo StudyFi Lab, ktorá beží priamo v prehliadači.
Lineárne vyhľadávanie prechádza prvky jeden po druhom, takže v najhoršom prípade potrebuje n krokov — O(n). Binárne vyhľadávanie funguje len na zoradenom poli: pozrie sa do stredu a podľa výsledku zahodí celú polovicu. Po každom kroku zostane najviac polovica, preto stačí najviac ⌈log₂(n+1)⌉ krokov — O(log n). Pre 40 prvkov je to 6 krokov namiesto 40.
Vyskúšaj: Nastav 40 prvkov a hľadaj poslednú hodnotu. Potom zvoľ číslo, ktoré v poli nie je — koľko krokov potrebuje každé vyhľadávanie, kým to zistí?
Časté otázky
Čo ukazuje pokus „Lineárne vs. binárne vyhľadávanie“?
Lineárne vyhľadávanie prechádza prvky jeden po druhom, takže v najhoršom prípade potrebuje n krokov — O(n). Binárne vyhľadávanie funguje len na zoradenom poli: pozrie sa do stredu a podľa výsledku zahodí celú polovicu. Po každom kroku zostane najviac polovica, preto stačí najviac ⌈log₂(n+1)⌉ krokov — O(log n). Pre 40 prvkov je to 6 krokov namiesto 40.
Ako si vyskúšať „Lineárne vs. binárne vyhľadávanie“?
Nastav 40 prvkov a hľadaj poslednú hodnotu. Potom zvoľ číslo, ktoré v poli nie je — koľko krokov potrebuje každé vyhľadávanie, kým to zistí?
Učíš sa na test?
Nahraj svoje poznámky a StudyFi z nich urobí kartičky, testy a podcasty.