Binarno iskanje vs Linearno iskanje
Linearno iskanje, znano tudi kot zaporedno iskanje, je najpreprostejši algoritem iskanja. Na seznamu išče določeno vrednost s preverjanjem vseh elementov 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) in tako zmanjša čas, potreben za iskanje določenega 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. Vhod v metodo linearnega iskanja je zaporedje (na primer matrika, zbirka ali niz) in element, ki ga je treba iskati. Izhod je true, če je navedeni element znotraj navedenega zaporedja ali false, če ni v zaporedju. Ker ta metoda preverja vse elemente na seznamu, dokler ne najde določenega elementa, bo v najslabšem primeru prešla vse elemente na seznamu, preden bo našla potrebni element. Kompleksnost linearnega iskanja je o (n). Zato velja za prepočasnega za uporabo pri iskanju elementov na velikih seznamih. A 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 predmeta 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 z uporabo samo spodnje polovice razvrščenega seznama. Če je iskani element manjši od srednjega elementa, znova zažene metodo z uporabo samo zgornje polovice razvrščenega seznama. Če iskanega elementa ni na seznamu, bo metoda vrnila enolično vrednost, ki to kaže. Zato binarna metoda iskanja razpolovi število primerjanih elementov (v vsaki ponovitvi), odvisno od rezultata primerjave. Posledičnobinarno iskanje se izvaja v logaritemskem času, kar ima za posledico povprečno uspešnost o (log n).
Kakšna je razlika med binarnim iskanjem in linearnim iskanjem?
Čeprav sta linearno iskanje in binarno iskanje način iskanja, imata več razlik. Medtem ko binarno iskanje deluje na razvrščenih seznamih, lahko iskanje linij deluje tudi na nesortiranih seznamih. Razvrščanje seznama ima na splošno povprečno zapletenost n log n. linearno iskanje je enostavno in enostavno za izvedbo kot binarno iskanje. Vendar je linearno iskanje prepočasno, da bi ga lahko uporabljali z velikimi seznami zaradi povprečne zmogljivosti o (n) primerov. Po drugi strani pa binarno iskanje velja za učinkovitejšo metodo, ki bi jo lahko uporabili na velikih seznamih. Toda izvajanje binarnega iskanja bi lahko bilo precej zapleteno in študija je pokazala, da je natančno kodo za binarno iskanje mogoče najti le v petih od dvajsetih knjig.
