ebSkola

7. tēma / 7.1

7.1 Meklēšanas pamati

Stundas uzdevums: Saprast atšķirību starp "meklēt visu pēc kārtas" un "gudro meklēšanu". Tu izveidosi savus pirmos meklēšanas algoritmus, lai atrastu svarīgus spēles elementus spēlētāja inventārā, un sapratīsi, kāpēc datu kārtošana ir kritiska ātrdarbībai.

SR 2.4.19. (Gatavi algoritmi tipveida uzdevumu risēšanai - meklēšana)

70 min plāns: Teorija un paraugs (~10 min) · 1. uzdevums (~15 min) - uzraksti lineāro meklēšanu · 2. uzdevums (~25 min) - uzraksti bināro meklēšanu sakārtotā sarakstā · 3. uzdevums (~20 min) - saskaiti soļus abiem un salīdzini. Papildu uzdevumu sāc tikai tad, ja pārējie trīs ir gatavi.

Pirms sāc: atver VS Code un izveido failu mekle_skaitli.py. Binārā meklēšana strādā tikai sakārtotā sarakstā - to atceries visu stundu.

Teorija: Meklēšanas algoritmi

  • Algoritms: Precīza instrukciju virkne konkrēta uzdevuma veikšanai (piemēram, kā atrast "Slepeno atslēgu" starp 1000 priekšmetiem).
  • Lineārā meklēšana (Linear Search):
    • Pārbauda katru elementu pēc kārtas no sākuma līdz beigām.
    • Darbojas ar jebkuru sarakstu (arī nesakārtotu).
    • Sliktākais scenārijs: Jāpārbauda pilnīgi visi elementi. Ļoti lēna lielos datu apjomos.
  • Binārā meklēšana (Binary Search):
    • Izmanto "skaldi un valdi" principu, katrā solī atmetot pusi no nederīgajiem datiem.
    • Pārbauda saraksta vidējo elementu. Ja meklētais ir lielāks, meklē labajā pusē; ja mazāks - kreisajā.
    • Kritisks nosacījums: Darbojas tikai sakārtotos sarakstos.
    • Zibensātra: Pat 1 miljona elementu sarakstā vajadzēs maksimāli 20 pārbaudes.
# Lineārā meklēšana - O(n)
def linear(saraksts, mērķis):
    for i, x in enumerate(saraksts):
        if x == mērķis:
            return i
    return -1

# Binārā meklēšana - O(log n) - saraksts JĀBŪT sakārtotam
def binary(saraksts, mērķis):
    lo, hi = 0, len(saraksts) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if saraksts[mid] == mērķis: return mid
        elif saraksts[mid] < mērķis: lo = mid + 1
        else: hi = mid - 1
    return -1

Vides sagatavošana (Windows)

Pirms rakstām kodu, izveidosim pareizu struktūru mūsu jaunajai tēmai.

  1. Atver PowerShell vai Command Prompt.
  2. Izveido jaunu mapi 7. tēmai un ieej tajā, izpildot šīs komandas:

mkdir Tema7_Algoritmi
cd Tema7_Algoritmi
  1. Izveido tukšu Python failu šodienas stundai un atver to kodu redaktorā (piemēram, VS Code):

ni mekle_skaitli.py
code .

Praktiskie uzdevumi

1. uzdevums -

Uzraksti lineāro meklēšanu

Beigās funkcija pateiks, kurā vietā sarakstā atrodas meklētais ID.

  1. Izveido sarakstu ar 20 nejaušiem ID numuriem, izmantojot random.randint.
  2. Uzraksti funkciju def linear_search(saraksts, mekletais):.
  3. Izmanto funkcijā ciklu for i, elements in enumerate(saraksts):.
  4. Atgriez indeksu i, tiklīdz elements sakrīt ar meklēto.
  5. Atgriez funkcijas beigās -1, ja nekas netika atrasts.
  6. Izsauc funkciju gan ar esošu, gan neesošu numuru.

Gatavs, kad: ar esošu numuru funkcija atgriež indeksu, ar neesošu - -1, nevis kļūdu.

2. uzdevums -

Uzraksti bināro meklēšanu sakārtotā sarakstā

Beigās meklēšana atmetīs pusi saraksta katrā solī.

  1. Sakārto sarakstu ar saraksts.sort().
  2. Uzraksti funkciju def binary_search(saraksts, mekletais):.
  3. Ieraksti tajā apaksa = 0 un augsa = len(saraksts) - 1.
  4. Uzraksti ciklu while apaksa <= augsa:.
  5. Izrēķini vidu ar vidus = (apaksa + augsa) // 2.
  6. Pārbīdi apaksa vai augsa atkarībā no salīdzinājuma.
  7. Izsauc abas funkcijas ar to pašu skaitli un salīdzini rezultātus.

Gatavs, kad: abas funkcijas atrod vienu un to pašu skaitli, un binārā strādā tikai pēc sort().

3. uzdevums -

Saskaiti soļus abiem un salīdzini

Beigās tu skaitļos redzēsi, cik lielā mērā binārā meklēšana ir ātrāka.

  1. Pievieno abām funkcijām skaitītāju soli = 0.
  2. Palielini to katrā cikla iterācijā.
  3. Atgriez gan indeksu, gan soļu skaitu.
  4. Palaid abas ar sarakstu no 20 elementiem un pieraksti soļus.
  5. Palielini sarakstu līdz 1000 elementiem un palaid vēlreiz.
  6. Pieraksti, cik reižu pieauga soļu skaits katrai metodei.
  7. Pieraksti vienu secinājumu: kāpēc binārajai meklēšanai vajag sakārtotu sarakstu.

Gatavs, kad: palielinot sarakstu 50 reizes, lineārās meklēšanas soļi aug ļoti strauji, bet binārās - tikai par dažiem.

Papildu uzdevums - Izmēģini iebūvēto index()

Ja pamatdarbs ir gatavs, salīdzini savu kodu ar Python gatavo risinājumu.

  1. Izmanto saraksts.index(mekletais) tā paša skaitļa meklēšanai.
  2. Salīdzini rezultātu ar savas funkcijas atbildi.
  3. Izsauc index() ar neesošu skaitli un pieraksti kļūdu.
  4. Ieliec to try/except ValueError blokā.
  5. Pieraksti, ar ko index() uzvedība atšķiras no tavas funkcijas.

Gatavs, kad: index() ar neesošu skaitli met ValueError, bet tava funkcija atgriež -1.

Koda piemērs (binārās meklēšanas robežas - grūtākā daļa)

# Grūtākā vieta nav pati ideja "atmetam pusi", bet DIVAS ROBEŽAS.
# Ja apaksa/augsa pārbīda nepareizi, cikls vai nu izlaiž atbildi,
# vai griežas mūžīgi. Tāpēc pēc salīdzinājuma vidus VIENMĒR tiek izslēgts.

def binary_search(saraksts, mekletais):
    apaksa = 0
    augsa = len(saraksts) - 1
    soli = 0

    while apaksa <= augsa:          # <= , nevis < - citādi pazūd pēdējais elements
        soli += 1
        vidus = (apaksa + augsa) // 2

        if saraksts[vidus] == mekletais:
            return vidus, soli
        elif saraksts[vidus] < mekletais:
            apaksa = vidus + 1       # +1 izslēdz jau pārbaudīto vidu
        else:
            augsa = vidus - 1        # -1 izslēdz jau pārbaudīto vidu

    return -1, soli

dati = sorted([42, 15, 8, 99, 23, 4, 16, 81, 100, 5, 1, 33, 50, 60, 11])
vieta, soli = binary_search(dati, 42)
print(f"Atrasts indeksā {vieta}, izmantojot {soli} soļus.")
15 elementu sarakstā skaitlis tiek atrasts 3-4 soļos, nevis 10. Ja aizmirsti +1 vai -1, cikls nekad nebeidzas - tieši tur iestrēgst lielākā daļa skolēnu.