Vadovėlis/Paieška ir Rikiavimas

Atlikęs praeito skyriaus uždavinius, jau žinai daug apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosim įgytomis žiniomis ir susipažinsim su labai dažnai susidruriamais uždaviniais: paieška ir rikiavimas.

Paieškos algoritmai naudojami norint rasti konkretų elementą sąraše ar duomenų masyve. Yra keletas paieškos algoritmų, tačiau parodysiu du dažniausiai naudojaus - tiesinė paieška ir dvejetainė paieška.

Tiesinė paieška

Tiesinė paieška - tai paprastas paieškos algoritmas, kuris, ieškodamas tikslinės reikšmės, peržiūri kiekvieną sąrašo elementą. Pažiūrėk į tiesinės paieškos funkcijos pavyzdį "Python" kalba:

def tiesinė_paieška(sąrašas, ieškomas_žodis):
    for i in range(len(sąrašas)):
        if sąrašas[i] == ieškomas_žodis:
            return i
    return -1  # ieškomas_žodis nerastas

Ši funkcija priima masyvą sąrašas ir tikslinę reikšmę ieškomas_žodis ir grąžina tikslinės reikšmės indeksą masyve. Jei tikslinė vertė nerandama masyve, funkcija grąžina -1. Labai praprasta ir aišku.

Dvejetainė paieška

Kita vertus, dvejetainė paieška yra efektyvesnis paieškos algoritmas, kuris veikia tik rūšiuotuose masyvuose. Jis veikia pakartotinai dalydamas paieškos intervalą per pusę, kol randama tikslinė reikšmė. Painu? Daug aiškiau bus pažiūrėjus šį pavyzdį:

def dvejetainė_paieška(sąrašas, tikslas):
    # išsisaugom sąrašo pirmą ir paskutinį indeksą
    apačia = 0
    viršus = len(sąrašas) - 1
    
    while apačia <= viršus:
        # aatrandame vidurį pagal formulę: (pradžios indeksas + pabaigos indeksas) padalintas per pusę, be liekanos
        viduriukas = (apačia + viršus) // 2
        # patikriname, ar `viduriukas` indekse yra mūsų ieškomas tikslas, ir jį atradus grąžiname indeksą.
        if sąrašas[viduriukas] == tikslas:
            return viduriukas
        # jeigu ne, tai pagal tai, kurioje pusėje yra ieškomas elementas pakeičiame viršutinį arba apatinį indeksą
        elif sąrašas[viduriukas] < tikslas:
            apačia = viduriukas + 1
        else:
            viršus = viduriukas - 1
        # ir kartojame iš naujo, bet jau su nauju, per pus mažesniu rėžiu
    
    return -1  # tikslas nerastas

sąrašas = [1,2,3,4,5,6,7,8,9,10]
print(dvejetainė_paieška(sąrašas, 7)) # 6

Panagrinėkim detaliai, kaip vyksta procesas. Ieškome, kur yra skaičius 7, sąraše [1,2,3,4,5,6,7,8,9,10]. Funkcijos pradžios kintamieji:

apačia = 0
viršus = 9 (ilgis 10 - 1 )

Pirmas `while` ciklas:

viduriukas = 4 # (0 + 9) // 2
sąrašas[4] saugo reikšmę 5. Ne mūsų ieškomas skaičius.
kadangi tikslas yra surasti 7, tai mūsų kito ciklo metu ieškosime viršutinėje sąrašo dalyje, todėl nusistatome naują apačios reikšmę, viduriukas + 1.
apačia = 4 + 1 = 5.

Antras `while` ciklas:

viduriukas = 7 # (5 + 9) // 2
sąrašas[7] saugo reikšmę 8. Jau arčiau, bet ne dar vis ne mūsų ieškoma reikšmė 7. Nustatome šįkartą naują viršutinę reikšmę, viduriukas - 1
viršus = 7 - 1 = 6

Trečias `while` ciklas:

viduriukas = 5 # (5 + 6) // 2
sąrašas[5] saugo reikmę 6. Vėl pro šalį. Nustatome naują apatinę reikšmę:
apačia = 5 + 1 = 6

Ketvirtas `while` ciklas:

viduriukas = 6 # (6 + 6) // 2
sąrašas[6] saugo reikšmę 7. Valio! Radom. Grąžinam indeksą 7.

Atkreipk dėmesį, kad dvejetainės paieškos algoritmas atrado reikšmę per 4 ciklus. Kaip manai, kiek ciklų prireiktų tiesinės paieškos algoritmui? Pasufleruosiu... Daugiau :)