Razlika med binarnim iskanjem in linearnim iskanjem

Binarno iskanje vs Linearno iskanje

Linearno iskanje, imenovano tudi zaporedno iskanje, je najpreprostejši algoritem iskanja. Poišče določeno vrednost na seznamu s preverjanjem vseh elementov na seznamu. Binarno iskanje je tudi metoda, ki se uporablja za iskanje določene vrednosti na razvrščenem seznamu. Binarni način iskanja prepolovi število preverjenih elementov (v vsaki ponovitvi) in zmanjša čas, potreben za iskanje določenega predmeta na seznamu.

Kaj je linearno iskanje?

Linearno iskanje je najpreprostejši način iskanja, ki vsak element zaporedno preverja, dokler ne najde določenega elementa. Vhod v način linearnega iskanja je zaporedje (na primer matrika, zbirka ali niz) in element, ki ga je treba iskati. Izhod je resničen, če je določeni element znotraj navedenega zaporedja ali napačen, če ni v zaporedju. Ker ta metoda preveri vse elemente na seznamu, dokler ne najde podanega elementa, bo v najslabšem primeru skozi vse elemente na seznamu, preden najde želeni element. Kompleksnost linearnega iskanja je o (n). Zato se šteje, da je prepočasen, da bi ga uporabljali pri iskanju elementov na velikih seznamih. Toda to je zelo preprosto in lažje izvedljivo.

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 primerjanjem iskanega elementa z elementi na sredini seznama. Če primerjava ugotovi, da sta dva elementa enaka, se metoda ustavi in ​​vrne položaj elementa. Če je iskani element večji od srednjega, začne postopek znova uporabiti le spodnjo polovico razvrščenega seznama. Če je iskani element manjši od srednjega, začne postopek znova le z zgornjo polovico razvrščenega seznama. Če iskani element ni na seznamu, bo metoda vrnila edinstveno vrednost, ki to kaže. Zato binarni način iskanja prepolovi število primerjanih elementov (v vsaki ponovitvi), odvisno od rezultata primerjave. Posledično se binarno iskanje izvaja v logaritmičnem času, kar ima za posledico o (log n) povprečno velikost.

Kakšna je razlika med binarnim iskanjem in linearnim iskanjem?

Čeprav sta linearno in binarno iskanje iskalna načina, imata več razlik. Medtem ko binarno iskanje deluje na razvrščenih seznamih, lahko iskanje linij deluje tudi na nerazvrščenih seznamih. Razvrščanje seznama ima na splošno povprečno zapleteno število n log n. linearno iskanje je preprosto in preprosto za izvedbo kot binarno iskanje. Toda linearno iskanje je prepočasno, da bi ga lahko uporabljali na velikih seznamih zaradi svoje (n) povprečne uspešnosti. Po drugi strani velja, da je binarno iskanje učinkovitejša metoda, ki jo je mogoče uporabiti na velikih seznamih. Toda izvajanje binarnega iskanja bi bilo lahko zelo težavno, raziskava pa je pokazala, da je mogoče natančno kodo za binarno iskanje najti le v petih od dvajsetih knjig.