Paaiškinti tiesiniai ir dvejetainiai paieškos algoritmai

Galimybė ieškoti tam tikrų duomenų yra svarbus informatikos aspektas. Paieškos algoritmai naudojami tam tikram duomenų rinkinio elementui ieškoti.

Algoritmai grąžina loginį rezultatą (teisingą ar klaidingą) į paieškos užklausą. Jie taip pat gali būti modifikuoti, kad būtų pateikta santykinė rastos vertės padėtis.

Šiame straipsnyje algoritmai sutelks dėmesį į vertės egzistavimą.

Linijinės paieškos algoritmai

Linijinė paieška taip pat žinoma kaip nuosekli paieška. Šio tipo paieškoje kiekviena sąrašo vertė yra aplankyta po vieną, tvarkingai, tikrinant, ar norima vertė yra.

Algoritmas tikrina vertę pagal vertę, kol randa ieškomą vertę arba pritrūksta ieškomų verčių. Kai pritrūksta ieškomų verčių, tai reiškia, kad jūsų paieškos užklausos sąraše nėra.

Nuoseklus paieškos algoritmas į parametrus įtraukia verčių sąrašą ir norimą sąrašo elementą. Grąžinimo rezultatas inicijuojamas kaip Netiesa ir pasikeis į Tiesa kai randama norima vertė.

Kaip pavyzdį žr. Toliau pateiktą „Python“ diegimą:

def linearSearch (mano sąrašas, elementas):

rasta = klaidinga

indeksas = 0

o indeksas

jei mano sąrašas [indeksas] == elementas:

rasta = tiesa

Kitas:

indeksas = indeksas+1

sugrįžimas rastas

Algoritmo analizė

Geriausias scenarijus įvyksta, kai norimas elementas yra pirmasis sąraše. Blogiausias atvejis būna tada, kai norimas elementas yra paskutinis sąraše (n -asis elementas). Todėl linijinės paieškos laiko sudėtingumas yra O (n).

Vidutinis atvejo scenarijus aukščiau pateiktame algoritme yra n/2.

Susijęs: Kas yra „Big-O“ žymėjimas?

Modifikuota linijinė paieška

Svarbu žinoti, kad naudojamas algoritmas daro prielaidą, kad jam pateikiamas atsitiktinis elementų sąrašas. Tai yra, sąrašo elementai nėra konkrečios eilės.

Tarkime, kad daiktai buvo tam tikra tvarka, tarkime, nuo mažiausios iki didžiausios. Skaičiuojant būtų galima pasiekti tam tikrą pranašumą.

Paimkite pavyzdį, kai pateiktame sąraše ieškote 19: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Pasiekus 23 metus paaiškėtų, kad ieškomo elemento sąraše nėra. Todėl nebėra svarbu toliau ieškoti likusių sąrašo elementų.

Dvejetainiai paieškos algoritmai

Jūs matėte, kaip užsakytas sąrašas gali sumažinti reikalingą skaičiavimą. Dvejetainis paieškos algoritmas dar labiau išnaudoja šį efektyvumą, kurį suteikia užsakytas sąrašas.

Algoritmas prasideda paėmus užsakyto sąrašo vidurinę vertę ir patikrinus, ar tai norima vertė. Jei ne, tada tikrinama, ar ji yra mažesnė, ar didesnė už norimą vertę.

Jei jis yra mažesnis, nereikia tikrinti apatinės sąrašo pusės. Priešingu atveju, jei jis didesnis, jis pereina į viršutinę sąrašo pusę.

Susijęs: Kas yra rekursija ir kaip ją naudoti?

Nepriklausomai nuo to, kuris antrinis sąrašas (kairysis ar dešinysis) pasirinktas, vėl bus nustatyta vidurinė vertė. Vertė dar kartą tikrinama, jei tai reikalinga vertė. Jei ne, patikrinama, ar ji yra mažesnė ar didesnė už prašomą vertę.

Šis procesas kartojamas, kol randama vertė, jei ji yra.

Žemiau pateiktas „Python“ diegimas skirtas dvejetainiam paieškos algoritmui.

def binarySearch (mano sąrašas, elementas):

maža = 0

didelis = len (mano sąrašas) - 1

rasta = klaidinga

nors žemas <= didelis ir nerastas:

vidurys = (žemas + aukštas) // 2

jei mano sąrašas [viduryje] == elementas:

rasta = tiesa

elif elementas

aukštas = vidurys - 1

Kitas:

žemas = vidurys + 1

sugrįžimas rastas

Algoritmo analizė

Geriausiu atveju scenarijus atsiranda tada, kai norimas elementas yra vidurinis elementas. Tačiau blogiausias scenarijus nėra toks paprastas. Atlikite toliau pateiktą analizę:

Po pirmojo palyginimo bus palikta n/2 elementų. Po antrojo liks n/4 daiktų. Po trečiojo n/8.

Atkreipkite dėmesį, kad elementų skaičius mažėja perpus, kol pasiekia n/2i, kur i yra palyginimų skaičius. Po visų padalijimų gauname tik 1 elementą.

Tai reiškia:

n/2i = 1

Todėl dvejetainė paieška yra O (log n).

Pereinama prie rūšiavimo

Dvejetainėje paieškoje mes svarstėme atvejį, kai nurodytas masyvas jau buvo užsakytas. Bet tarkime, kad turite neužsakytą duomenų rinkinį ir norite jame atlikti dvejetainę paiešką. Ką tu darytum?

Atsakymas paprastas: surūšiuokite. Kompiuterių moksle yra nemažai rūšiavimo būdų, kurie buvo gerai ištirti. Vienas iš šių metodų, kurį galite pradėti studijuoti, yra atrankos rūšiavimo algoritmas, o mes taip pat turime daug vadovų, susijusių su kitomis sritimis.

Kaip naudoti atrankos rūšiavimą

Atrankos rūšiavimas yra šiek tiek sudėtingas pradedantiesiems, tačiau tai nėra per daug sudėtinga, kai tik įsisąmoninate dalykus.

Skaityti toliau

Apie autorių