10. Keresések
Lineáris keresés rendezett sorozatban:
Pszeudokód(X: Sorozat amiben keresünk, N: Sorozat elemszáma, Y: Keresendő elem, VAN: Logikai változó, SORSZ: Talált elem sorszáma):
Eljárás LineárisKeresés(X, N, Y, VAN, SORSZ)
i<-1
Ciklus amíg(i<=N) és (X[i] < Y)
i<-i+1
Ciklus vége
VAN<-(i<=N) és (X[i]=Y)
Ha VAN akkor
SORSZ<-i
Elágazás vége
Eljárás vége
Futási idő:
- Minimális lépésszám: 1 (Előállhat ez az érték akkor is ha Y nincs benne a sorozatban!)
- Maximális lépésszám: N
- Átlagos Lépésszám: (N+1)/2 (Nem függ attól, hogy Y benne van-e a sorozatban!)
Logaritmikus keresés:
Alapötlet: Vizsgáljuk meg a sorozat középső elemét. Ha a keresett elem kisebb mint a sorozat középső tagja, akkor a középső elem előtt lesz a keresett elem. Ha nagyobb, akkor utána található. Ha megegyezik, megvan a keresett elem. Folytatjuk a felezést míg végül megtaláljuk az elemet.
Pszeudokód(X: Sorozat amiben keresünk, N: Sorozat elemszáma, Y: Keresendő elem, VAN: Logikai változó, SORSZ: Talált elem sorszáma):
Eljárás LogaritmikusKeresés(X, N, Y, VAN, SORSZ)
E<-1; U<-N
Ciklus
K<-EgészrészFüggvény((E+U)/2)
Elágazás
Y<X[K] esetén
U<-K-1
Y>X[K]esetén
E<-K+1
Elágazás vége
Amíg (E<=U)és(X[K]!=Y)
VAN<-(E<=U)
Ha VAN akkor
SORSZ<-K
Elágazás vége
Eljárás vége
Futási idő:
- Minimális lépésszám: 1 (Ha a középső elem az Y)
- Maximális lépésszám: 1+log2N (egészrész)
- Átlagos lépésszám: log2N (egészrész)
Programozási tételek megvalósítása rendezett sorozatok esetén:
Rendezett sorok esetén javíthatunk a következő programozási tételeken is a logaritmikus kereséssel: Eldöntés, Kiválogatás, Kiválasztás, Megszámlálás
Eldöntés:
Pszeudokód(X: Sorozat ,N: Sorozat elemszáma ,Y: Keresett elem ,VAN: Logikai változó):
Eljárás Eldöntés(X, N, Y, VAN)
E<-1; U<-N
Ciklus
K<-EgészrészFüggvény((E+U)/2)
Elágazás
Y<X[K] esetén
U<-K-1
Y>X[K]esetén
E<-K+1
Elágazás vége
Amíg (E<=U)és(X[K]!=Y)
VAN<-(E<=U)
Eljárás vége
Kiválasztás:
Biztosan tudjuk, hogy benne van a sorozatban Y!
Pszeudokód(X: Sorozat amiben keresünk, N: Sorozat elemszáma, Y: Keresendő elem, SORSZ: Talált elem sorszáma):
Eljárás LogaritmikusKeresés(X, N, Y, SORSZ)
E<-1; U<-N
Ciklus
K<-EgészrészFüggvény((E+U)/2)
Elágazás
Y<X[K] esetén
U<-K-1
Y>X[K]esetén
E<-K+1
Elágazás vége
Amíg (E<=U)és(X[K]!=Y)
SORSZ<-K
Eljárás vége
Kiválogatás:
- Az azonos értékű elemek egymás mellet helyezkednek el
- A logaritmikus kereséssel megkeresünk egyet
- És ezután megkeressük, hogy melyik indexen helyezkedik el az első(E) és utolsó(U) ilyen elem
- Visszatérési érték az E és U lesz
- Ha megvan E és U akkor a megszámlálás egyszerű: DB=U-E+1
Pszeudokód(X: Sorozat amiben keresünk, N: Sorozat elemszáma, Y: Keresendő elem, VAN: Logikai változó, E: Első keresett elem, U: Utolsó keresett elem):
Eljárás LogaritmikusKeresés(X, N, Y, VAN, E, U)
E<-1; U<-N
Ciklus
K<-EgészrészFüggvény((E+U)/2)
Elágazás
Y<X[K] esetén
U<-K-1
Y>X[K]esetén
E<-K+1
Elágazás vége
Amíg (E<=U)és(X[K]!=Y)
VAN<-(E<=U)
Ha VAN akkor
E<-K
Ciklus amíg (E>1) és (X[E-1]=Y)
E<-E-1
Ciklus vége
U<-K
Ciklus amíg (U<N) és (X[U+1]=Y)
U<-U+1
Ciklus vége
Elágazás vége
Eljárás vége
Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 9. előadás diasor
Kommentek
Powered by Facebook Comments