Iskanje - skrčeno

Iskanje - skrčeno

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

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

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 - 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)

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);
}

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

  • 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%