Izskaidroti lineārie un binārie meklēšanas algoritmi

Spēja meklēt dažus datus ir svarīgs datorzinātņu aspekts. Meklēšanas algoritmi tiek izmantoti, lai datu kopā meklētu noteiktu vienumu.

Algoritmi meklēšanas vaicājumam atgriež Būla rezultātu (patiesu vai nepatiesu). Tos var arī mainīt, lai sniegtu atrastās vērtības relatīvo stāvokli.

Šajā rakstā algoritmi koncentrēsies uz vērtības esamības noteikšanu.

Lineārās meklēšanas algoritmi

Lineāro meklēšanu sauc arī par secīgu meklēšanu. Šāda veida meklēšanā katra saraksta vērtība tiek kārtoti apskatīta pa vienam, vienlaikus pārbaudot, vai vēlamā vērtība pastāv.

Algoritms pārbauda vērtību pēc vērtības, līdz atrod meklēto vērtību vai beidzas meklētās vērtības. Ja meklēšanai trūkst vērtību, tas nozīmē, ka jūsu meklēšanas vaicājums sarakstā nepastāv.

Secīgs meklēšanas algoritms kā parametrus ņem vērtību sarakstu un vēlamo vienumu sarakstā. Atgriešanās rezultāts tiek inicializēts kā Nepatiess un mainīsies uz Taisnība kad tiek atrasta vēlamā vērtība.

Kā piemēru skatiet tālāk norādīto Python ieviešanu:

def linearSearch (mylist, item):

atrasts = nepatiess

indekss = 0

kamēr indekss

ja mans saraksts [indekss] == vienums:

atrasts = taisnība

cits:

indekss = indekss+1

atdeve atrasta

Algoritmu analīze

Labākais gadījums rodas, ja vēlamais vienums ir pirmais sarakstā. Sliktākais gadījums rodas, ja vēlamais vienums ir pēdējais sarakstā (n. Vienums). Tāpēc lineārās meklēšanas laika sarežģītība ir O (n).

Vidējais scenārijs iepriekšminētajā algoritmā ir n/2.

Saistīts: Kas ir Big-O apzīmējums?

Modificēta lineārā meklēšana

Ir svarīgi zināt, ka izmantotais algoritms pieņem, ka tam tiek nodrošināts nejaušs vienumu saraksts. Tas ir, saraksta vienumi nav noteiktā secībā.

Pieņemsim, ka preces bija noteiktā secībā, piemēram, no mazākā līdz lielākajam. Aprēķinos būtu iespējams iegūt zināmas priekšrocības.

Ņemiet piemēru, meklējot 19 dotajā sarakstā: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Pēc 23 gadu vecuma sasniegšanas kļūtu skaidrs, ka meklētais vienums sarakstā neeksistē. Tāpēc vairs nebūtu svarīgi turpināt meklēt pārējos saraksta vienumus.

Binārie meklēšanas algoritmi

Jūs esat redzējuši, kā sakārtots saraksts var samazināt nepieciešamo aprēķinu. Binārās meklēšanas algoritms vēl vairāk izmanto šo efektivitāti, ko nodrošina sakārtots saraksts.

Algoritms sākas, ņemot sakārtotā saraksta vidējo vērtību un pārbaudot, vai tā ir vēlamā vērtība. Ja tā nav, tad tiek pārbaudīta vērtība, vai tā ir mazāka vai lielāka par vēlamo vērtību.

Ja tas ir mazāks, tad nav jāpārbauda saraksta apakšējā puse. Pretējā gadījumā, ja tas ir lielāks, tas pāriet uz saraksta augšējo pusi.

Saistīts: Kas ir rekursija un kā to izmantot?

Neatkarīgi no izvēlētā apakšsaraksta (pa kreisi vai pa labi) atkal tiks noteikta vidējā vērtība. Vērtība tiek vēlreiz pārbaudīta, ja tā ir nepieciešamā vērtība. Ja tā nav, tiek pārbaudīts, vai tā ir mazāka vai lielāka par pieprasīto vērtību.

Šo procesu atkārto, līdz tiek atrasta vērtība, ja tā ir.

Tālāk redzamā Python ieviešana ir paredzēta binārajam meklēšanas algoritmam.

def binarySearch (mylist, item):

zems = 0

augsts = len (mylist) - 1

atrasts = nepatiess

kamēr zems <= augsts un nav atrasts:

vidus = (zems + augsts) // 2

ja mans saraksts [vidū] == vienums:

atrasts = taisnība

elif vienums

augsts = vidus - 1

cits:

zems = vidus + 1

atdeve atrasta

Algoritmu analīze

Labākais gadījums rodas, ja tiek atzīts, ka vēlamais vienums ir vidējais vienums. Sliktākais scenārijs tomēr nav tik vienkāršs. Izpildiet tālāk sniegto analīzi:

Pēc pirmā salīdzinājuma n/2 vienumi tiks atstāti. Pēc otrā tiks atstāti n/4 priekšmeti. Pēc trešās, n/8.

Ievērojiet, ka vienību skaits samazinās uz pusi, līdz sasniedz n/2i, kur i ir salīdzinājumu skaits. Pēc visas sadalīšanas mēs iegūstam tikai 1 vienumu.

Tas nozīmē:

n/2i = 1

Tāpēc binārā meklēšana ir O (log n).

Pārejam uz kārtošanu

Binārā meklēšanā mēs izskatījām gadījumu, kad dotais masīvs jau bija pasūtīts. Bet pieņemsim, ka jums bija nesakārtota datu kopa un jūs vēlējāties tajā veikt bināro meklēšanu. Ko tu darītu?

Atbilde ir vienkārša: sakārtojiet to. Datorzinātnē ir vairākas kārtošanas metodes, kas ir labi izpētītas. Viens no šiem paņēmieniem, ko varat sākt studēt, ir atlases kārtošanas algoritms, lai gan mums ir daudz ceļvežu, kas saistīti arī ar citām jomām.

Kā izmantot atlases kārtošanu

Atlases kārtošana iesācējiem ir nedaudz sarežģīta, lai to saprastu, taču tas nav pārāk sarežģīti, tiklīdz esat apguvis lietas.

Lasīt Tālāk

Par autoru