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 úgy keres meg egy elemet egy listában, hogy ismételten kettéosztja, és csak azt a felét tartja meg, amelyik tartalmazza a keresett elemet.
Segítségével gyorsan leszűkíthetjük a keresett 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 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 benne a listában.
- Egyébként ismételd meg a folyamatot a lista még ki nem zárt részén.
Íme egy példa:
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 a 23-at hasonlítjuk össze a középső elemmel, a 16-tal.
- Mivel a 23 nagyobb, mint a 16, kizárhatjuk a lista bal felét, így
[23, 28, 32] marad.
- Ezután a 23-at hasonlítjuk össze 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.
Tippek
A Haskell számos tömbtípust támogat. Ez a feladat a Data.Array modulban található módosíthatatlan, boxolt, nem szigorú tömböket használja. Ezeknek a tömböknek a használatáról bővebben itt olvashatsz:
Opcionális kiegészítésként ehhez a feladathoz próbáld meg úgy megírni a find függvényt, hogy tetszőleges határokkal rendelkező tömbökkel is működjön, például olyan tömbökkel, amelyeknél az első index nem feltétlenül 0.
