Iskanje

Iskanje

Avtor: Matija Lokar

Več o projektu...

Iskanje v tabeli

  • Ali je element v tabeli

    • Neurejena tabela
    • Urejena tabela

  • Najmanjši v tabeli

    • iterativno
    • z rekurzijo

  • Največji v tabeli

    • iterativno
    • z rekurzijo
  • k-ti po velikosti

Iskanje v tekstovni datoteki

  • Zaporedoma beremo vrstice, dokler ne najdemo podatka

  • Metoda

    •  public static bool AliObstaja( string imeDat, RegStev x) 
    • Ali v datoteki imeDat obstaja vrstica z zapisom Ob-stev, ki predatavlja isto reg. številko kot x?

  • Denimo da je datoteka urejena – ali lahko kaj pridobimo

    • Ne prav dosti, le da iskanje v primeru, da številke ni, lahko prekinemo prej

  • Metoda

    • public static bool AliObstaja( string imeDat, RegStev x, bool urejena)
    • Ali v datoteki imeDat obstaja vrstica z zapisom Ob-stev, ki predatavlja isto reg. številko kot x?
    • Če je urejena == true , je datoteka urejena
    • To upoštevamo pri iskanju

Iskanje v tekstovni datoteki - metoda

  • Odpremo datoteko za branje in preberemo prvo vrstico

  • Dokler ni konca datoteke

    • Če je vrstica enaka x.ToString , vrnemo true
    • Če je urejena true in vrstica večja, vrnemo false
    • Preberemo vrstico
  • Če smo prišli do konca datoteke, vrnemo false
  • Pozor – preden vrnemo rezultat (v vsakem primeru) zapremo datoteko

Ali je element v tabeli

  • Če tabela ni urejena

    • Sprehod preko celotne tabele

  • Če je tabela urejena

    • Bisekcija

Iskanje v neurejeni tabeli

  • Iskanje v neurejeni tabele
  • Algoritem:

  • Preglej vse elemente v tabeli

    • Če je i-ti enak, vrni true
  • Če si pregledal vse, vrni false

Poišči v tabeli nizov

public bool Poisci(string[] tab, string kaj){
  // ali je kaj v tabeli tab
  int dol = tab.Length;
  for (int i = 0; i < dol; i++) {
    if (tab[i] == kaj) return true;
  }
  return false; // pregledali smo vse,
                // pa ga ni
}

Bisekcija

  • Bisekcija ali razpolavljanje

    • bisekcija je v numerični matematiki postopek za iskanje ničel zveznih funkcij
    • bisekcija v ravninski geometriji je postopek iskanja simetrale dane množice točk (npr.: bisekcija kota = določanje simetrale kota ipd)
    • bisekcija v računalništvu je postopek za preiskovanje urejenih seznamov.
  • Delitev tabele na pol
  • Tabela mora biti urejena

Bisekcija - algoritem

  • Pogledamo srednji element

  • Če je enak iskanemu,

    • Hura!

  • Če je srednji elt manjši od iskanega,

    • potem iskanega elementa v prvem delu zagotovo ni
    • Zato iščemo v desnem delu (s tem smo velikost problema razpolovili)

  • Če pa je večji,

    • potem je iskani elementa morda v prvem delu
    • Zato ga iščemo v levem delu (s tem smo velikost problema razpolovili)

Bisekcija - algoritem

  • s = srednji element tabele

  • Če x == s

    • Končamo z odgovorom true

  • Če x < s

    • Odgovor je: kar vrne bisekcija na levem delu
  • Odgovor je kar vrne bisekcija na desnem delu

Bisekcija - primer

  • Imamo urejeno tabelo dvanajstih elementov, in iščemo število .

    • 1, 3, 4, 7, 10, 17, 18, 23, 50, 71, 73, 80

  • Koraki:

    • j = 114, , , iščemo v prvi polovici iskalnega območja
    • , , , iščemo v drugi polovici iskalnega območja
    • , , , vrnemo rezultat 3.
(iskanje_10.png)

Metoda z zanko

public bool Bisekcija(int tab[], int iskano) {
    int doKam = tab.Length - 1; // desna meja iskanja
    int odKje = 0, sred; //
    while(odKje <= doKam) { // dokler je še kaj podatkov za iskanje
        sred = (odKje + doKam) / 2; // indeks sredine dela
                                    // kjer iščemo
        if(tab[sred] < iskano)
            odKje = sred + 1; // iščemo desno
        else
            if(tab[sred] > iskano)
               doKam = sred - 1;
            else // tab[sred] == iskano
                return true;
    }
    return false; // ni ga!
}

Kaj pa to kje je?

  • Kaj spremeniti, če želimo vrniti mesto v tabeli, kjer je iskani podatek

    • Kako povedati, da podatka ni?
    • Recimo -1: podatka ni v tabeli
public int Bisekcija(int tab[], int odK, int doK, int iskano) {
    int doKam = doK; // desna meja iskanja
    int odKje = odK, sred; //
    while(odKje <= doKam) { // dokler je še kaj podatkov za iskanje
        sred = (odKje + doKam) / 2; // indeks sredine dela
                                    // kjer iščemo
        if(tab[sred] < iskano)
            odKje = sred + 1; // iščemo desno
        else
            if(tab[sred] > iskano)
               doKam = sred - 1;
            else // tab[sred] == iskano
                return sred;
    }
    return -1; // ni ga!
}

Rekurzija : ideja

  • Idejo da osnovni algoritem

  • Bisekcija(tabela, x)

    • s = srednji element tabele

    • Če x == s

      • Končamo z odgovorom true

    • Če x < s

      • return Bisekcija(levi del tabele)
    • return Bisekcija(desni del tabele)

  • Kaj pa ustavitveni pogoj

    • Če iščemo podatek med 1 eltom
    • Če iščemo podatek med 0 elementi (če tabele ni!)

Metoda malega Frančka

public bool Bisekcija(int tab[], int iskano) {
  // ali je podatek iskano v tabeli tab
  if (tab.Length == 0) // če ni elementov, ga zagotovo ni!
     return false;
  int sreda = tab.Length / 2; // indeks srednjega elementa
  if (iskano == tab[sreda]) return true; // hura, našli smo ...
  if (iskano < tab[sreda]) { // iščemo v levem delu
    // potrebujemo tabelo za levi del
    int[] tabLevo = new int[sreda]; // levo je sreda elementov
    for (int i = 0; i < sreda; i++) // preložimo
       tabLevo[i] = tab[i];
    return Bisekcija(tabLevo, iskano);
   }
   // iščemo desno
   // potrebujemo tabelo za desni del
   int[] tabDesno = new int[sreda]; // tudi desno je sreda elementov
    for (int i = 0; i < sreda; i++) // preložimo
       tabDesno[i] = tab[sreda + 1 + i];
    return Bisekcija(tabDesno, iskano);
}

Franček odraste

  • Ali bi šlo brez dodatnih tabel?

  • Posplošimo

    • Metoda, ki išče podatek v delu tabele
  • public static bool Bisekcija(int[] tab,  int odKje, int doKam, int iskani) {
  • Ali je element iskani v delu tabele od indeksa odKje do indeksa doKam?

  • "prava" metoda

    • public static bool Bisekcija(int[] tab,  int iskani) {
          return Bisekcija(tab, 0, tab.Length -1, iskani);
      }

Rekurzivna metoda odraslega Frančka

public bool Bisekcija(int tab[], int odKje, int doKam, int iskano) {
  // ali je podatek iskano v delu tabele tab
  if (odKje > doKam) // če ni elementov, ga zagotovo ni!
     return false;
  int sreda = (odKje + doKam) / 2; // indeks srednjega elementa
  if (iskano == tab[sreda]) return true; // hura, našli smo ...
  if (iskano < tab[sreda]) { // iščemo v levem delu
      return Bisekcija(tab, odKje, sreda – 1, iskano);
   }
   // iščemo desno
   return Bisekcija(tab, sreda + 1, doKam, iskano);
}

Najmanjši v tabeli

  • Kaj vračamo

    • Podatek
    • Indeks (kje je najmanjši)

  • Algoritem

    • Iterativno

      • Beri: s klasično zanko (for ali while ali ...)

    • Rekurzivno

      • ;-)

Najmanjši v tabeli – s "klasično" zanko

  • Prvi v tabeli je kandidat za najmanjšega

  • Po k korakih:

    • Kandidat za najmanjšega med prvimi k elementi tabele
    • Pogledamo k+1-tega
    • Če je manjši, on postane kandidat

Najmanjši v tabeli - rekurzivno

  • Razdelimo tabelo na pol

    • Problem smo razdelili na dva podproblema iste vrste (a manjša)
  • Poiščemo najmanjšega v obeh polovicah

  • Rešitev je manjši od obeh

    • Združevanje rešitev

  • Ustavi?

    • Poišči najmanjšega, če imamo le enega (ali pa dva)

  • Da ne bo spet mali Franček preveč pameten

    • Dve metodi

      • Poiščemo najmanjšega v delu tabele (rekurzija)
      • Poiščemo najmanjšega v celi tabeli (le klic gornje metode)

Poišči k-ti element po velikosti

  • Dana je tabela števil
  • Radi bi poiskali npr. 5 element po velikosti
  • Ali pa tretjega ...
  • Največjega ali najmanjšega

  • Tretji po velikosti

    • 12, 4, 2, 5, 1, 6, 2, 4, 8
    • Tretji po velikosti je 2 (če je torej več enakih, upoštevamo vse!)

Poišči k-ti element po velikosti

Ideje:

  • Uredimo

    • Smisleno le, če pogosto potrebujemo različne k-te

  • Poiščemo največjega, naslednjega največjega ...

    • K-krat ponovi

      • Poišči največjega (ali najmanjšega)

        • Pri tem ne smemo upoštevati najdenih v prejšnjem koraku
    • K "glavnih korakov" urejanja z izbiranjem
    • Iskanje tretjega največjega hitrejše, kot iskanje npr. 123-tega

Poišči k-ti element po velikosti

  • Rekurzija?

    • Razpolovimo tabelo
    • Poiščemo petega v prvem in petega v drugem delu
    • Združi?

  • Kaj pa, če bi delili tabelo kako drugače?

    • Elementi levo morajo biti "v odnosu" z elementi desno

Poišči k-ti element po velikosti

  • Deli kot pri hitrem urejanju
  • Če je v levem delu >= k elementov, ga poiščemo levo
  • Če je levo > k (recimo j) elementov, poiščemo k – j tega v desnem delu.

Primer

70, 75, 80, 85, 60, 55, 50, 45, 223, 22, 56, 185, 82, 5, 15, 14

  • Iščemo sedmega
  • Deli:
    22, 14, 15, 5, 60, 55, 50, 45, 56, 70, 223, 185, 82, 85, 80, 75
  • V prvem delu je 10 elementov, zato iščemo naprej v tem delu. Še vedno sedmega.
    5, 14, 15, 22, 60, 55, 50, 45, 56, 70
  • V prvem delu so 4 elementi, zato iščemo naprej v drugem delu. Iščemo 7 – 4 = tretjega.
    56, 55, 50, 45, 60, 70
  • V prvem delu je 5 elementov, zato iščemo naprej v tem delu. Še vedno tretjega.
    45, 55, 50, 56, 60
  • V prvem delu so 4 elementi, zato iščemo naprej v tem delu. Še vedno tretjega.
    45, 55, 50, 56
  • V prvem delu je 1 element, zato iščemo naprej v drugem delu. Tam iščemo 3 – 1 = drugega.
    50, 55, 56
  • V prvem delu sta dva elementa, zato iščemo naprej v tem delu. Še vedno drugega.
    50, 55
  • V prvem delu je 1 element, zato iščemo naprej v drugem delu. Tam iščemo 2 – 1 = prvega.
  • 55 je iskani element!
0%
0%