Prije razumijevanja razlika između linearnog i binarnog pretraživanja, prvo bismo trebali znati odvojeno linearno i binarno pretraživanje.
Što je linearna pretraga?
Linearno pretraživanje također je poznato kao sekvencijalno pretraživanje koje jednostavno skenira svaki element odjednom. Pretpostavimo da želimo pretražiti element u nizu ili popisu; jednostavno izračunamo njegovu duljinu i ne skačemo ni na jednu stavku.
Razmotrimo jednostavan primjer.
Pretpostavimo da imamo niz od 10 elemenata kao što je prikazano na slici ispod:
Gornja slika prikazuje niz tipa znakova koji ima 10 vrijednosti. Ako želimo pretraživati 'E', tada pretraživanje počinje od 0thelement i skenira svaki element dok se element, tj. 'E' ne pronađe. Ne možemo izravno skočiti s 0thelement do 4thelement, tj. svaki element se skenira jedan po jedan dok se element ne pronađe.
Složenost linearnog pretraživanja
Kako linearna pretraga skenira svaki element jedan po jedan sve dok se element ne pronađe. Ako se broj elemenata povećava, povećava se i broj elemenata koji se skeniraju. Možemo reći da je vrijeme potrebno za pretraživanje elemenata proporcionalno je broju elemenata . Stoga je složenost u najgorem slučaju O(n)
Što je binarno pretraživanje?
Binarno pretraživanje je pretraživanje u kojem se srednji element izračunava kako bi se provjerilo je li manji ili veći od elementa koji se traži. Glavna prednost korištenja binarnog pretraživanja je da ne skenira svaki element na popisu. Umjesto skeniranja svakog elementa, vrši pretraživanje do polovice popisa. Dakle, binarnom pretraživanju potrebno je manje vremena za pretraživanje elementa u usporedbi s linearnim pretraživanjem.
Onaj preduvjet binarnog pretraživanja je da niz treba biti sortiran, dok linearna pretraga radi i na sortiranom i na nesortiranom nizu. Algoritam binarnog pretraživanja temelji se na tehnici podijeli pa vladaj, što znači da će niz dijeliti rekurzivno.
U binarnom pretraživanju koriste se tri slučaja:
Slučaj 1: podaci
Slučaj 2: data>a[mid] then right=mid-1
Slučaj 3: data = a[mid] // element je pronađen
U gornjem slučaju, ' a ' je naziv niza, sredina je indeks elementa izračunat rekurzivno, podaci je element koji se traži, lijevo označava lijevi element niza i pravo označava element koji se nalazi na desnoj strani niza.
Razumimo rad binarnog pretraživanja kroz primjer.
Pretpostavimo da imamo niz veličine 10 koji je indeksiran od 0 do 9 kao što je prikazano na slici ispod:
Želimo tražiti 70 elemenata iz gornjeg niza.
Korak 1: Prvo izračunavamo srednji element niza. Razmatramo dvije varijable, tj. lijevu i desnu. U početku, lijevo =0 i desno=9 kao što je prikazano na donjoj slici:
Srednja vrijednost elementa može se izračunati kao:
Prema tome, mid = 4 i a[mid] = 50. Element koji se traži je 70, tako da a[mid] nije jednako podacima. Slučaj 2 je zadovoljen, tj. data>a[mid].
Korak 2: Kako je data>a[mid], tako se vrijednost lijevo povećava za mid+1, tj. lijevo=mid+1. Vrijednost mid je 4, tako da vrijednost lijevo postaje 5. Sada imamo podniz kao što je prikazano na slici ispod:
Sada opet, srednja vrijednost se izračunava pomoću gornje formule, a vrijednost mid postaje 7. Sada se srednja vrijednost može predstaviti kao:
Na gornjoj slici možemo uočiti da su a[mid]>data, tako da će opet vrijednost mid biti izračunata u sljedećem koraku.
Korak 3: Kao [mid]>podatak, vrijednost right se smanjuje za mid-1. Vrijednost sredine je 7, tako da vrijednost desne strane postaje 6. Niz se može predstaviti kao:
Vrijednost mid će se ponovno izračunati. Vrijednosti lijevog i desnog su 5 odnosno 6. Stoga je vrijednost mid 5. Sada se mid može predstaviti u nizu kao što je prikazano u nastavku:
Na gornjoj slici možemo primijetiti da [sredinom]
Korak 4: Kao [sredina] Sada se vrijednost mid ponovno izračunava pomoću formule o kojoj smo već govorili. Vrijednosti lijevog i desnog su 6 odnosno 6, tako da vrijednost sredine postaje 6 kao što je prikazano na donjoj slici: Na gornjoj slici možemo vidjeti da je a[mid]=data. Dakle, pretraga je završena, a element je uspješno pronađen. Sljedeće su razlike između linearnog i binarnog pretraživanja: Opis Linearno pretraživanje je pretraživanje koje pronalazi element na popisu uzastopnim pretraživanjem elementa dok se element ne pronađe na popisu. S druge strane, binarno pretraživanje je pretraživanje koje pronalazi srednji element na popisu rekurzivno dok se srednji element ne podudara s traženim elementom. Rad obje pretrage Linearno pretraživanje počinje pretraživanje od prvog elementa i skenira jedan po jedan element bez preskakanja na sljedeći element. S druge strane, binarno pretraživanje dijeli niz na pola izračunavanjem srednjeg elementa niza. Provedba Linearno pretraživanje može se implementirati na bilo kojoj linearnoj podatkovnoj strukturi kao što je vektor, jednostruko povezana lista, dvostruko povezana lista. Nasuprot tome, binarno pretraživanje može se implementirati na one strukture podataka s dvosmjernim obilaskom, tj. obilaskom naprijed i natrag. Složenost Linearno pretraživanje je jednostavno za korištenje, ili možemo reći da je manje složeno jer elementi za linearno pretraživanje mogu biti raspoređeni u bilo kojem redoslijedu, dok u binarnom pretraživanju, elementi moraju biti raspoređeni u određenom redoslijedu. Razvrstani elementi Elementi za linearno pretraživanje mogu se poredati nasumičnim redoslijedom. U linearnom pretraživanju nije obavezno da su elementi raspoređeni sortiranim redoslijedom. S druge strane, u binarnom pretraživanju elementi moraju biti raspoređeni po sortiranom redoslijedu. Može se poredati u rastućem ili u opadajućem redoslijedu, au skladu s tim, algoritam će se promijeniti. Kako binarno pretraživanje koristi sortirani niz, potrebno je umetnuti element na odgovarajuće mjesto. Nasuprot tome, linearno pretraživanje ne treba sortirani niz, tako da se novi element može lako umetnuti na kraj niza. Pristup Linearna pretraga koristi iterativni pristup za pronalaženje elementa, pa je također poznata kao sekvencijalni pristup. Nasuprot tome, binarno pretraživanje izračunava srednji element niza, pa koristi pristup podijeli pa vladaj. Skup podataka Linearno pretraživanje nije prikladno za veliki skup podataka. Ako želimo pretraživati element, koji je zadnji element niza, linearna pretraga će započeti pretragu od prvog elementa i nastaviti do posljednjeg elementa, tako da bi vrijeme potrebno za pretragu elementa bilo veliko. S druge strane, binarno pretraživanje je prikladno za veliki skup podataka jer traje manje vremena. Ubrzati Ako je skup podataka velik u linearnom pretraživanju, tada bi računalni trošak bio visok, a brzina bi postala spora. Ako je skup podataka velik u binarnom pretraživanju, tada bi računalni trošak bio manji u usporedbi s linearnim pretraživanjem, a brzina postaje velika. Dimenzije Linearno pretraživanje može se koristiti i na jednodimenzionalnom i na višedimenzionalnom nizu, dok se binarno pretraživanje može implementirati samo na jednodimenzionalnom nizu. Učinkovitost Linearno pretraživanje je manje učinkovito kada uzmemo u obzir velike skupove podataka. Binarno pretraživanje je učinkovitije od linearnog pretraživanja u slučaju velikih skupova podataka. Pogledajmo razlike u tabelarnom obliku. 
Razlike između linearnog i binarnog pretraživanja
java string charat
Osnova usporedbe Linearna pretraga Binarno pretraživanje Definicija Linearna pretraga započinje pretragu od prvog elementa i uspoređuje svaki element s traženim elementom sve dok se element ne pronađe. Pronalazi položaj traženog elementa pronalaženjem srednjeg elementa niza. Sortirani podaci U linearnom pretraživanju, elementi ne moraju biti raspoređeni po sortiranom redoslijedu. Preduvjet za binarno pretraživanje je da elementi moraju biti raspoređeni sortiranim redoslijedom. Provedba Linearno pretraživanje može se implementirati na bilo kojoj linearnoj podatkovnoj strukturi kao što je niz, povezani popis itd. Implementacija binarnog pretraživanja je ograničena jer se može implementirati samo na one strukture podataka koje imaju dvosmjerno prolaženje. Pristup Temelji se na sekvencijalnom pristupu. Temelji se na pristupu zavadi pa vladaj. Veličina Poželjno je za skupove podataka male veličine. Poželjno je za skupove podataka velike veličine. Učinkovitost Manje je učinkovit u slučaju skupova podataka velike veličine. Učinkovitiji je u slučaju skupova podataka velike veličine. Najgori scenarij U linearnoj pretrazi, najgori mogući scenarij za pronalaženje elementa je O(n). U binarnom pretraživanju, najgori mogući scenarij za pronalaženje elementa je O(log2n). Najbolji scenarij U linearnom pretraživanju, najbolji scenarij za pronalaženje prvog elementa na popisu je O(1). U binarnom pretraživanju, najbolji scenarij za pronalaženje prvog elementa na popisu je O(1). Dimenzionalni niz Može se implementirati i na jednodimenzionalnom i na višedimenzionalnom polju. Može se implementirati samo na višedimenzionalnom polju.