Lineární vs. binární vyhledávání
Lineární vs. binární vyhledávání je interaktivní pokus z aplikace Algoritmy v akci, bezplatné simulace ze StudyFi Lab, která běží přímo v prohlížeči.
Lineární vyhledávání prochází prvky jeden po druhém, takže v nejhorším případě potřebuje n kroků — O(n). Binární vyhledávání funguje jen na seřazeném poli: podívá se doprostřed a podle výsledku zahodí celou polovinu. Po každém kroku zbude nejvýš polovina, proto stačí nejvýš ⌈log₂(n+1)⌉ kroků — O(log n). Pro 40 prvků je to 6 kroků místo 40.
Vyzkoušej: Nastav 40 prvků a hledej poslední hodnotu. Pak zvol číslo, které v poli není — kolik kroků potřebuje každé vyhledávání, než to zjistí?
Časté otázky
Co ukazuje pokus „Lineární vs. binární vyhledávání“?
Lineární vyhledávání prochází prvky jeden po druhém, takže v nejhorším případě potřebuje n kroků — O(n). Binární vyhledávání funguje jen na seřazeném poli: podívá se doprostřed a podle výsledku zahodí celou polovinu. Po každém kroku zbude nejvýš polovina, proto stačí nejvýš ⌈log₂(n+1)⌉ kroků — O(log n). Pro 40 prvků je to 6 kroků místo 40.
Jak si vyzkoušet „Lineární vs. binární vyhledávání“?
Nastav 40 prvků a hledej poslední hodnotu. Pak zvol číslo, které v poli není — kolik kroků potřebuje každé vyhledávání, než to zjistí?
Učíš se na test?
Nahraj svoje zápisky a StudyFi z nich udělá kartičky, testy a podcasty.