Bevezetés
Egy csapat matematikusra bukkantál, akik egyben énekes-dalszerzők is.
Minden kedvenc számukhoz írtak egy dalt, és ahogy sejtheted, rengeteg kedvenc számuk van (például a 0, a 73 vagy a 6174).
Kíváncsi vagy, milyen dal szól a kedvenc számodról, de ennyi dal között eltartana egy ideig, mire megtalálod a megfelelőt.
Szerencsére a dalaikat egy lejátszási listába szedték, a címük szerint rendezve, a cím pedig egyszerűen az a szám, amelyről a dal szól.
Rájössz, hogy bináris kereséssel gyorsan megtalálhatod a dalt, ha ismered a címét.
Utasítások
A feladatod, hogy megvalósítsd a bináris keresés algoritmusát.
A bináris keresés algoritmusa úgy keres meg egy elemet egy listában, hogy ismételten kettéosztja a listát, és csak azt a felét tartja meg, amelyikben a keresett elem van.
Segítségével gyorsan leszűkíthetjük az elem lehetséges helyeit, amíg meg nem találjuk, vagy amíg az összes lehetséges helyet ki nem zártuk.
A bináris keresés csak akkor működik, ha a lista rendezve van.
Az algoritmus így néz ki:
- Keresd meg egy rendezett lista középső elemét, és hasonlítsd össze a keresett elemmel.
- Ha a középső elem maga a keresett elem, akkor készen is vagyunk!
- Ha a középső elem nagyobb a keresett elemnél, akkor kizárhatjuk azt az elemet és az utána következő összes elemet.
- Ha a középső elem kisebb a keresett elemnél, akkor kizárhatjuk azt az elemet és az előtte lévő összes elemet.
- Ha a lista minden elemét kizártuk, akkor a keresett elem nincs a listában.
- Ellenkező esetben ismételd meg az eljárást a lista még ki nem zárt részén.
Nézzünk egy példát:
Tegyük fel, hogy a 23-as számot keressük a következő rendezett listában: [4, 8, 12, 16, 23, 28, 32].
- Először összehasonlítjuk a 23-at a középső elemmel, a 16-tal.
- Mivel a 23 nagyobb, mint a 16, kizárhatjuk a lista bal felét, így csak
[23, 28, 32] marad.
- Ezután összehasonlítjuk a 23-at az új középső elemmel, a 28-cal.
- Mivel a 23 kisebb, mint a 28, kizárhatjuk a lista jobb felét:
[23].
- Megtaláltuk a keresett elemet.
