Binarno iskanje v primerjavi z linearnim iskanjem
Linearno iskanje, znano tudi kot zaporedno iskanje, je najpreprostejši iskalni algoritem. Išče določeno vrednost na seznamu tako, da preveri vsak element na seznamu. Binarno iskanje je tudi metoda, ki se uporablja za iskanje določene vrednosti na razvrščenem seznamu. Metoda binarnega iskanja prepolovi število preverjenih elementov (v vsaki ponovitvi), kar skrajša čas, potreben za iskanje danega elementa na seznamu.
Kaj je linearno iskanje?
Linearno iskanje je najpreprostejša metoda iskanja, ki zaporedno preverja vsak element na seznamu, dokler ne najde določenega elementa. Vnos metode linearnega iskanja je zaporedje (kot je niz, zbirka ali niz) in element, ki ga je treba iskati. Izhod je resničen, če je navedeni element v podanem zaporedju, ali napačen, če ni v zaporedju. Ker ta metoda preverja vsak element na seznamu, dokler ne najde določenega elementa, bo v najslabšem primeru pregledala vse elemente na seznamu, preden najde zahtevani element. Kompleksnost linearnega iskanja je o(n). Zato velja, da je prepočasen za uporabo pri iskanju elementov na velikih seznamih. Toda to je zelo preprosto in lažje za izvedbo.
Kaj je binarno iskanje?
Binarno iskanje je tudi metoda, ki se uporablja za iskanje določenega elementa na razvrščenem seznamu. Ta metoda se začne s primerjavo iskanega elementa z elementi na sredini seznama. Če primerjava ugotovi, da sta elementa enaka, se metoda ustavi in vrne položaj elementa. Če je iskani element večji od srednjega elementa, znova zažene metodo samo z uporabo spodnje polovice razvrščenega seznama. Če je iskani element manjši od srednjega elementa, znova zažene metodo samo z uporabo zgornje polovice razvrščenega seznama. Če iskanega elementa ni na seznamu, bo metoda vrnila edinstveno vrednost, ki to označuje. Zato metoda binarnega iskanja prepolovi število primerjanih elementov (v vsaki ponovitvi), odvisno od rezultata primerjave. Posledično se binarno iskanje izvaja v logaritemskem času, kar ima za posledico o(log n) povprečno zmogljivost med malimi in malimi črkami.
Kakšna je razlika med binarnim iskanjem in linearnim iskanjem?
Čeprav sta linearno in binarno iskanje metodi iskanja, imata več razlik. Medtem ko binarno iskanje deluje na razvrščenih seznamih, lahko linijsko iskanje deluje tudi na nerazvrščenih seznamih. Razvrščanje seznama ima na splošno povprečno kompleksnost črk in črk n log n. linearno iskanje je preprosto in enostavno za implementacijo kot binarno iskanje. Toda linearno iskanje je prepočasno za uporabo z velikimi seznami zaradi o(n) povprečne zmogljivosti med malimi in malimi črkami. Po drugi strani velja, da je binarno iskanje učinkovitejša metoda, ki bi jo lahko uporabili z velikimi seznami. Toda implementacija binarnega iskanja bi lahko bila precej težavna in študija je pokazala, da je natančno kodo za binarno iskanje mogoče najti le v petih od dvajsetih knjig.
