Võimalus teatud andmeid otsida on arvutiteaduse oluline aspekt. Otsingualgoritme kasutatakse andmekogumist konkreetse üksuse otsimiseks.

Algoritmid tagastavad otsingupäringule loogilise tulemuse (õige või vale). Neid saab ka muuta, et anda leitud väärtuse suhteline asukoht.

Selle artikli puhul keskenduvad algoritmid väärtuse olemasolu kindlakstegemisele.

Lineaarse otsingu algoritmid

Lineaarset otsingut tuntakse ka järjestikotsinguna. Seda tüüpi otsingu korral külastatakse loendi iga väärtust ükshaaval korrapäraselt, kontrollides soovitud väärtuse olemasolu.

Algoritm kontrollib väärtust väärtuste kaupa, kuni leiab otsitava väärtuse või otsitavad väärtused saavad otsa. Kui otsitava väärtused on otsas, tähendab see, et teie otsingupäringut pole loendis olemas.

Järjestikuse otsingu algoritm võtab parameetriteks väärtuste loendi ja loendis soovitud üksuse. Tagastamistulemus lähtestatakse kujul Vale ja muutub Tõsi kui soovitud väärtus on leitud.

Vaadake näiteks Pythoni rakendust allpool:

def linearSearch (mylist, item):

leitud = vale

indeks = 0

samas kui indeks

kui minu loend [indeks] == üksus:

leitud = tõsi

muidu:

indeks = indeks+1

tagasitulek leitud

Algoritmi analüüs

Parim stsenaarium juhtub siis, kui soovitud üksus on loendis esimene. Halvim juhtum tekib siis, kui soovitud üksus on loendis viimane (n -nda üksus). Seetõttu on lineaarse otsingu ajaline keerukus O (n).

Ülaltoodud algoritmi keskmine juhtum on n/2.

Seotud: Mis on Big-O märge?

Muudetud lineaarne otsing

Oluline on teada, et kasutatav algoritm eeldab, et sellele esitatakse juhuslik üksuste loend. See tähendab, et loendiüksused pole kindlas järjekorras.

Oletame, et esemed olid kindlas järjekorras, näiteks väikseimast suuremani. Arvutamisel oleks võimalik teatud eeliseid saavutada.

Võtke näide sellest, et otsite antud loendist 19: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Pärast 23 -aastaseks saamist selguks, et otsitavat üksust loendis pole. Seetõttu poleks enam oluline jätkata ülejäänud loendiüksuste otsimist.

Kahendotsingu algoritmid

Olete näinud, kuidas järjestatud loend võib vähendada vajalikke arvutusi. Binaarotsingu algoritm kasutab seda tõhusust veelgi rohkem ära, kui tellitud loendi olemasolu.

Algoritm algab tellitud loendi keskmise väärtuse võtmisega ja kontrollib, kas see on soovitud väärtus. Kui ei, siis kontrollitakse väärtust, kas see on soovitud väärtusest väiksem või suurem.

Kui seda on vähem, pole vaja loendi alumist poolt kontrollida. Vastasel juhul, kui see on suurem, liigub see loendi ülemisse poole.

Seotud: Mis on rekursioon ja kuidas seda kasutada?

Olenemata sellest, kumb alamloend (vasak või parem) valitakse, määratakse uuesti keskmine väärtus. Väärtust kontrollitakse uuesti, kui see on nõutav väärtus. Kui ei, siis kontrollitakse, kas see on väiksem või suurem kui nõutud väärtus.

Seda protsessi korratakse, kuni väärtus leitakse, kui see on olemas.

Allpool olev Pythoni rakendus on mõeldud binaarse otsingu algoritmi jaoks.

def binarySearch (mylist, item):

madal = 0

kõrge = len (minu nimekiri) - 1

leitud = vale

samas madal <= kõrge ja ei leitud:

keskel = (madal + kõrge) // 2

kui minu loend [keskel] == üksus:

leitud = tõsi

elif item

kõrge = keskel - 1

muidu:

madal = keskel + 1

tagasitulek leitud

Algoritmi analüüs

Parim stsenaarium juhtub siis, kui soovitud üksus on keskmine. Halvim stsenaarium pole siiski nii lihtne. Järgige järgmist analüüsi:

Pärast esimest võrdlust jääb n/2 eset alles. Pärast teist jääb alles n/4 eset. Pärast kolmandat, n/8.

Pange tähele, et üksuste arv väheneb poole võrra, kuni jõuab n/2i, kus i on võrdluste arv. Pärast kogu jagamist saame lõpuks ainult 1 eseme.

See tähendab:

n/2i = 1

Seetõttu on binaarotsing O (log n).

Sortimise juurde liikumine

Binaarotsingus kaalusime juhtumit, kus antud massiiv oli juba tellitud. Kuid oletame, et teil oli tellimata andmekogum ja soovite selle abil binaarset otsingut teha. Mida sa teeksid?

Vastus on lihtne: sorteeri. Arvutiteaduses on mitmeid sorteerimistehnikaid, mida on hästi uuritud. Üks neist meetoditest, mida saate õppima asuda, on valiku sortimise algoritm, samas kui meil on palju juhendeid ka teiste valdkondadega.

JagaPiiksumaE -post
Valiku sortimise kasutamine

Valiku sorteerimine on algajatele natuke keeruline aru saada, kuid see pole liiga keeruline, kui olete asjad hoos.

Loe edasi

Seotud teemad
  • Programmeerimine
  • Tehnoloogia selgitatud
  • Programmeerimine
  • Algoritmid
  • Andmete analüüs
Autori kohta
Jerome Davidson (Avaldatud 21 artiklit)

Jerome on MakeUseOfi personalikirjanik. Ta hõlmab artikleid programmeerimise ja Linuxi kohta. Ta on ka krüptohuviline ja jälgib alati krüptotööstust.

Veel Jerome Davidsonilt

Telli meie uudiskiri

Liituge meie uudiskirjaga, et saada tehnilisi näpunäiteid, ülevaateid, tasuta e -raamatuid ja eksklusiivseid pakkumisi!

Tellimiseks klõpsake siin