Vsebina

• Primerjalna tabela
• Opredelitev linearnega iskanja
• Opredelitev binarnega iskanja
• Zaključek

Linearno iskanje in binarno iskanje sta dve metodi, za katere se uporablja niz iskanje elementi. Iskanje je postopek iskanja elementa v seznamu elementov, shranjenih v poljubnem vrstnem redu ali naključno.

Glavna razlika med linearnim iskanjem in binarnim iskanjem je, da binarno iskanje traja manj časa za iskanje elementov iz razvrščenega seznama elementov. Zato sklepamo, da je učinkovitost binarnega iskanja večja od linearnega iskanja.

Druga razlika med obema je, da je predpogoj za binarno iskanje, tj. Elementi morajo biti razvrščeno medtem ko pri linearnem iskanju ni takšnega predpogoja. Čeprav obe metodi iskanja uporabljata različne tehnike, ki so opisane v nadaljevanju.

1. Primerjalna tabela
2. Opredelitev
3. Ključne razlike
4. Zaključek

Primerjalna tabela

Osnove za primerjavo	Linearno iskanje	Binarno iskanje
Časovna zapletenost	O (N)	O (dnevnik 2 N)
Najboljši čas	Prvi element O (1)	Sredinski element O (1)
Predpogoj za niz	Ni potrebno	Niz mora biti razvrščen
Najslabši primer za N število elementov	Ni potrebnih primerjav	Zaključi se lahko samo po dnevniku2N primerjav
Lahko se izvaja naprej	Array in Povezani seznam	Na povezanem seznamu ni mogoče neposredno izvajati
Vstavite operacijo	Enostavno se vstavi na koncu seznama	Za vzdrževanje razvrščenega seznama zahtevajte obdelavo, da jo vstavite na svojem primernem mestu.
Vrsta algoritma	Iterativne narave	Delite in osvajajte v naravi
Uporabnost	Enostaven za uporabo in nobenih naročenih elementov.	Kakor koli že, zahteven algoritem in elemente je treba organizirati po vrstnem redu.
Kode vrstice	Manj	Več

Opredelitev linearnega iskanja

Pri linearnem iskanju se vsak element matrike naloži drug za drugim v logičnem zaporedju in preveri, ali je želeni element ali ne. Iskanje ne bo uspešno, če do vseh elementov dostopate in želenega elementa ne najdete. V najslabšem primeru je število povprečnih primerov, ki jih bomo morda morali skenirati za polovico velikosti matrike (n / 2).

Zato je linearno iskanje lahko definirano kot tehniko, ki zaporedno prehaja matriko za iskanje danega elementa. Spodnji program prikazuje iskanje elementov matrike z iskanjem.

Učinkovitost linearnega iskanja

Učinkovitost tehnike določa časovna poraba ali število primerjav pri iskanju zapisa v iskalni tabeli. Če je želeni zapis na prvem mestu iskalne tabele, se opravi le ena primerjava. Ko je želen zapis zadnji, je treba opraviti n primerjav. Če naj bo zapis nekje v iskalni tabeli, bo v povprečju število primerjav (n + 1/2). Najslabši učinek te tehnike je, da O (n) pomeni vrstni red izvedbe.

Program C iskanje elementa z linearno tehniko iskanja.

#include #include void main () {int a, n, i, element, loc = -1; clrscr (); f (" nVnesite številko elementa:"); scanf ("% d", & n); f ("Vnesite številke: n"); za (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nVnesite številko, ki jo želite iskati:"); scanf ("% d", & element); za (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; odmor; }} if (loc> = 0) {f (" n% d najdemo v položaju% d:", element, loc + 1); } else {f (" n Postavka ne obstaja"); } getch (); }

Opredelitev binarnega iskanja

Binarno iskanje je izjemno učinkovit algoritem. Ta tehnika iskanja porabi manj časa pri iskanju določenega predmeta v minimalnih možnih primerjavah. Za binarno iskanje moramo najprej razvrstiti elemente matrike.

Logika te tehnike je podana spodaj:

• Najprej poiščite srednji element matrike.
• Srednji element matrike se primerja z elementom, ki ga je treba iskati.

Obstajajo trije primeri:

1. Če je element potreben element, je iskanje uspešno.
2. Ko je element manjši od želenega elementa, poiščite samo prvo polovico matrike.
3. Če je večji od želenega elementa, poiščite v drugi polovici matrike.

Ponavljajte iste korake, dokler se ne najde element ali izčrpa v iskalnem območju. V tem algoritmu se vsakokratno območje iskanja zmanjša. Zato je število primerjav največ log (N + 1). Kot rezultat, je to učinkovit algoritem v primerjavi z linearnim iskanjem, vendar je treba matrično vrsto razvrstiti, preden opravite binarno iskanje.

Program C najti element z binarno tehniko iskanja.

#include void main () {int i, beg, konec, sredina, n, iskanje, matrika; f ("Vnesite številko elementa n"); scanf ("% d", & n); f ("Vnesite% d številke n", n); za (i = 0; i <n; i ++) scanf ("% d", & matrika); f ("Vnesite številko za iskanje n"); scanf ("% d", & iskanje); beg = 0; konec = n - 1; sredina = (beg + konec) / 2; medtem ko (beg <= konec) {if (array <search) beg = sredina + 1; drugo če (array == iskanje) {f ("Iskanje je uspešno. n% d najdeno na lokaciji% d. n", iskanje, sredina + 1); odmor; } else end = sredina - 1; sredina = (beg + konec) / 2; } if (beg> end) f ("Iskanje je neuspešno!% d ni na seznamu. n", iskanje); getch (); }

1. Linearno iskanje je iterativno in uporablja zaporedni pristop. Po drugi strani pa binarno iskanje izvaja pristop delitve in osvajanja.
2. Časovna zahtevnost linearnega iskanja je O (N), medtem ko ima binarno iskanje O (dnevnik)₂N).
3. Najboljši čas pri linearnem iskanju je prvi element, tj. O (1). Nasprotno, pri binarnem iskanju gre za srednji element, to je O (1).
4. Pri linearnem iskanju je najslabši primer za iskanje elementa N število primerjav. V nasprotju s tem je dnevnik₂N število primerjav za binarno iskanje.
5. Linearno iskanje je mogoče izvesti tako v matriki kot na povezanem seznamu, medtem ko binarnega iskanja ni mogoče izvajati neposredno na povezanem seznamu.
6. Kot vemo, binarno iskanje zahteva razvrščen niz, kar je razlog. Za vzdrževanje razvrščenega seznama je potrebna obdelava za vstavljanje na svojem mestu. Nasprotno linearno iskanje ne potrebuje razvrščenih elementov, zato se elementi zlahka vstavijo na koncu seznama.
7. Linearno iskanje je enostavno za uporabo in ni potrebe po nobenih naročenih elementih. Po drugi strani je algoritem binarnega iskanja vendarle težaven in elementi so nujno razporejeni po vrstnem redu.

Zaključek

Tako linearni kot binarni algoritmi iskanja so lahko koristni glede na aplikacijo. Če je matrika struktura podatkov in so elementi razvrščeni v razvrščenem vrstnem redu, je prednostno binarno iskanje hitroiskanje. Če je povezan seznam podatkovna struktura ne glede na to, kako so elementi razporejeni, je linearno iskanje sprejeto zaradi nerazpoložljivosti neposrednega izvajanja algoritma binarnega iskanja.

Tipičnega algoritma Binarnega iskanja ni mogoče uporabiti na seznamu, ker je povezan seznam dinamičen in ni znano, kje je srednji element dejansko dodeljen. Zato je treba zasnovati različico algoritma binarnega iskanja, ki lahko deluje tudi na povezanem seznamu, ker je binarno iskanje hitrejše kot linearno iskanje.