Preden razumemo razlike med linearnim in binarnim iskanjem, moramo najprej poznati ločeno linearno in binarno iskanje.
Kaj je linearno iskanje?
Linearno iskanje je znano tudi kot zaporedno iskanje, ki preprosto skenira vsak element naenkrat. Recimo, da želimo iskati element v matriki ali seznamu; preprosto izračunamo njegovo dolžino in ne skočimo na noben element.
Poglejmo preprost primer.
Recimo, da imamo niz 10 elementov, kot je prikazano na spodnji sliki:
Zgornja slika prikazuje matriko znakovnega tipa z 10 vrednostmi. Če želimo iskati 'E', potem se iskanje začne od 0thelement in pregleduje vsak element, dokler element, tj. 'E', ni najden. Ne moremo neposredno skočiti z 0thelement do 4thelement, tj. vsak element se pregleda enega za drugim, dokler elementa ne najdemo.
Kompleksnost linearnega iskanja
Kot linearno iskanje skenira vsak element enega za drugim, dokler elementa ne najdemo. Če se število elementov poveča, se poveča tudi število elementov za skeniranje. Lahko rečemo, da je čas, potreben za iskanje elementov, je sorazmeren s številom elementov . Zato je kompleksnost v najslabšem primeru O(n)
Kaj je binarno iskanje?
Binarno iskanje je iskanje, pri katerem se srednji element izračuna, da se preveri, ali je manjši ali večji od elementa, ki ga je treba iskati. Glavna prednost uporabe binarnega iskanja je, da ne pregleduje vsakega elementa na seznamu. Namesto skeniranja vsakega elementa, izvede iskanje do polovice seznama. Torej binarno iskanje traja manj časa za iskanje elementa v primerjavi z linearnim iskanjem.
Tisti predpogoj za binarno iskanje je, da mora biti niz v razvrščenem vrstnem redu, medtem ko linearno iskanje deluje tako na razvrščenem kot nerazvrščenem nizu. Algoritem binarnega iskanja temelji na tehniki deli in vladaj, kar pomeni, da bo matriko delil rekurzivno.
Pri binarnem iskanju se uporabljajo trije primeri:
Primer 1: podatki
Primer 2: data>a[mid] then right=mid-1
Primer 3: data = a[mid] // element je najden
V zgornjem primeru ' a ' je ime matrike, sredina je indeks elementa, izračunan rekurzivno, podatke je element, ki ga je treba iskati, levo označuje levi element matrike in prav označuje element, ki se pojavi na desni strani matrike.
Razumejmo delovanje binarnega iskanja na primeru.
Recimo, da imamo niz velikosti 10, ki je indeksiran od 0 do 9, kot je prikazano na spodnji sliki:
Iskati želimo 70 elementov iz zgornje matrike.
Korak 1: Najprej izračunamo srednji element matrike. Upoštevamo dve spremenljivki, to je levo in desno. Sprva levo =0 in desno=9, kot je prikazano na spodnji sliki:
Srednjo vrednost elementa je mogoče izračunati kot:
Zato je mid = 4 in a[mid] = 50. Element, ki ga je treba iskati, je 70, zato a[mid] ni enako podatku. Izpolnjen je primer 2, tj. data>a[mid].
2. korak: Ker je data>a[mid], se vrednost levo poveča za mid+1, tj. levo=mid+1. Vrednost mid je 4, tako da vrednost left postane 5. Sedaj imamo podmatriko, kot je prikazano na spodnji sliki:
Ponovno se srednja vrednost izračuna z uporabo zgornje formule in vrednost mid postane 7. Sedaj je srednja vrednost lahko predstavljena kot:
Na zgornji sliki lahko opazimo, da je a[mid]>data, tako da bo ponovno vrednost mid izračunana v naslednjem koraku.
3. korak: Kot [mid]>podatek se vrednost desne zmanjša za mid-1. Vrednost mid je 7, tako da vrednost right postane 6. Matriko lahko predstavimo kot:
Vrednost sredine bo ponovno izračunana. Vrednosti za levo in desno sta 5 oziroma 6. Zato je vrednost mid 5. Zdaj je mid lahko predstavljen v matriki, kot je prikazano spodaj:
Na zgornji sliki lahko opazimo, da [sredi]
4. korak: Kot [sredi] Zdaj se vrednost sredine ponovno izračuna z uporabo formule, o kateri smo že razpravljali. Vrednosti za levo in desno sta 6 oziroma 6, tako da vrednost sredine postane 6, kot je prikazano na spodnji sliki: Na zgornji sliki lahko opazimo, da je a[mid]=data. Zato je iskanje končano in element je uspešno najden. Razlike med linearnim in binarnim iskanjem so naslednje: Opis Linearno iskanje je iskanje, ki najde element na seznamu tako, da zaporedno išče element, dokler elementa ne najdemo na seznamu. Po drugi strani pa je binarno iskanje iskanje, ki najde srednji element na seznamu rekurzivno, dokler se srednji element ne ujema z iskanim elementom. Delovanje obeh iskanj Linearno iskanje začne iskati od prvega elementa in pregleduje en element naenkrat, ne da bi skočil na naslednji element. Po drugi strani pa binarno iskanje matriko razdeli na polovico z izračunom srednjega elementa matrike. Izvedba Linearno iskanje se lahko izvede na kateri koli linearni podatkovni strukturi, kot je vektor, enojno povezan seznam, dvojno povezan seznam. Nasprotno pa se binarno iskanje lahko izvaja na tistih podatkovnih strukturah z dvosmernim prehodom, tj. prehodom naprej in nazaj. Kompleksnost Linearno iskanje je enostavno za uporabo oziroma lahko rečemo, da je manj kompleksno, saj so lahko elementi za linearno iskanje razporejeni v poljubnem vrstnem redu, pri binarnem iskanju pa morajo biti elementi razporejeni v določenem vrstnem redu. Razvrščeni elementi Elemente za linearno iskanje je mogoče razporediti v naključnem vrstnem redu. Pri linearnem iskanju ni obvezno, da so elementi razporejeni v razvrščenem vrstnem redu. Po drugi strani pa morajo biti pri binarnem iskanju elementi urejeni v razvrščenem vrstnem redu. Lahko se razvrsti v naraščajočem ali padajočem vrstnem redu in v skladu s tem se spremeni algoritem. Ker binarno iskanje uporablja razvrščeno matriko, je treba element vstaviti na pravo mesto. Nasprotno pa linearno iskanje ne potrebuje razvrščene matrike, tako da je mogoče nov element enostavno vstaviti na konec matrike. Pristop Linearno iskanje uporablja iterativni pristop za iskanje elementa, zato je znano tudi kot zaporedni pristop. Nasprotno pa binarno iskanje izračuna srednji element matrike, zato uporablja pristop deli in vladaj. Nabor podatkov Linearno iskanje ni primerno za velik nabor podatkov. Če želimo iskati element, ki je zadnji element niza, bo linearno iskanje začelo iskati od prvega elementa in se nadaljevalo do zadnjega elementa, zato bo čas iskanja elementa velik. Po drugi strani pa je binarno iskanje primerno za velik nabor podatkov, saj traja manj časa. Hitrost Če je nabor podatkov pri linearnem iskanju velik, bi bili računski stroški visoki, hitrost pa bi bila počasna. Če je nabor podatkov pri binarnem iskanju velik, bi bil računski strošek manjši v primerjavi z linearnim iskanjem, hitrost pa bi bila visoka. Dimenzije Linearno iskanje je mogoče uporabiti tako na enodimenzionalnem kot večdimenzionalnem nizu, medtem ko je binarno iskanje mogoče implementirati samo na enodimenzionalnem nizu. Učinkovitost Linearno iskanje je manj učinkovito, če upoštevamo velike nize podatkov. Binarno iskanje je v primeru velikih nizov podatkov učinkovitejše od linearnega iskanja. Oglejmo si razlike v obliki tabele. 
Razlike med linearnim in binarnim iskanjem
bfs proti dfs
Osnova primerjave Linearno iskanje Binarno iskanje Opredelitev Linearno iskanje začne iskati od prvega elementa in vsak element primerja z iskanim elementom, dokler elementa ne najdemo. Poišče položaj iskanega elementa tako, da poišče srednji element matrike. Razvrščeni podatki Pri linearnem iskanju ni treba, da so elementi razvrščeni po razvrščenem vrstnem redu. Predpogoj za binarno iskanje je, da morajo biti elementi razporejeni v razvrščenem vrstnem redu. Izvedba Linearno iskanje je mogoče implementirati na katero koli linearno podatkovno strukturo, kot je polje, povezan seznam itd. Implementacija binarnega iskanja je omejena, saj se lahko izvaja samo na tistih podatkovnih strukturah, ki imajo dvosmerno prečkanje. Pristop Temelji na sekvenčnem pristopu. Temelji na pristopu deli in vladaj. Velikost Zaželeno je za nize podatkov majhne velikosti. Zaželeno je za nabore podatkov velike velikosti. Učinkovitost Manj učinkovit je v primeru podatkovnih nizov velike velikosti. Učinkovitejši je v primeru podatkovnih nizov velike velikosti. Najslabši možni scenarij Pri linearnem iskanju je najslabši možni scenarij za iskanje elementa O(n). Pri binarnem iskanju je najslabši možni scenarij za iskanje elementa O(log2n). Najboljši možni scenarij Pri linearnem iskanju je najboljši primer za iskanje prvega elementa na seznamu O(1). Pri binarnem iskanju je najboljši primer za iskanje prvega elementa na seznamu O(1). Dimenzijski niz Lahko se implementira na eno in večdimenzionalno polje. Izvaja se lahko samo na večdimenzionalnem nizu.