A logaritmikus (bináris) keresés
Ez a cikk egy igen gyakran használt keresési algoritmust mutat be, a lineáris kereséssel ellentétben csak rendezett sorozaton működik, így hatékonysága nyilván jobb annál. Például, ha matematikajegy szerint vannak csoportosítva a diákok, nyilván könnyebb megtalálni azt a tizenkettedikes diákot, aki jeles matematikából, mint ha csak névsor szerint lennének rendezve.
Adott egy rendezett n elemű M sorozat és egy keresett elem (X). El kell dönteni, hogy szerepel-e a keresett elem a sorozatban, s ha igen, akkor megadjuk annak a sorszámát.
A megvalósítás gondolatmenete:
Elsőként a felezőpontban lévő elemet nézzük meg, hogy megegyezik-e a keresett elemmel. Ha nem egyezik meg X a felezőpontban talált elemmel, akkor két eset lehet. Ha nagyobb, akkor a felső részintervallumban, ha kisebb, akkor pedig az alsóban folytatjuk a keresést, míg az intervallum hossza 1 nem lesz.
Algoritmus mondatszerű leírással:
Eljárás logaritmikus_kereses:
also = 1
felso = n
Ciklus
kozep := Egeszrész((also + felso)/ 2)
Ha M[Kozep] < X Akkor
also = kozep + 1
Elágazás vége
Ha M[Kozep] > X Akkor
felso = kozep - 1
Elágazás vége
Mígnem Also > Felso És M[Kozep] = X
Ciklus vége
talalt = (also < = felso)
Ha talalt Akkor
sorszam = kozep
Elágazás vége
Eljárás vége.
Feladat:
Készítsünk programot, amely ismerőseink lakóhelye (városa) alapján megad egy Szekszárdon lakót (lakóhely szerint sorbarendezett listánk van)!
Program baratok:
also = 1
felso = 100
van = False
Ciklus
kozepso = Int((Also + Felso)/2)
Ha Baratok.Hely(kozepso) < "Szekszard" Akkor
also = kozepso + 1
Elágazás vége
Ha Baratok.Hely(kozepso) > "Szekszard" Then
felso = kozepso - 1
Elágazás vége
Mígnem (also > felso) And Baratok.Hely(kozepso) = ”Szekszard”
Ciklus vége
van = (also <= felso)
Ha van Akkor
sorszam = kozepso
Elágazás vége
Ki: ”A keresett szekszárdi barát:”, Baratok.Nev(sorszam))
Program vége.
Házi feladat:
Készítsünk játékot, amelyben egy véletlenszerűen generált 1 és 100 közötti számot kell kitalálni a lehető legkevesebb lépésben. A játék végén azt is közölnünk kell, hány lépésben találták ki a keresett számot.