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.
Kivételüzenetek
Néha szükség van arra, hogy kivételt dobj. Ilyenkor mindig adj meg egy értelmes hibaüzenetet, amely jelzi, mi a hiba forrása. Ettől olvashatóbb lesz a kódod, és a hibakeresést is nagyban megkönnyíti. Ha tudod, hogy a hiba forrása egy bizonyos típusú, dönthetsz úgy, hogy a beépített hibatípusok egyikét dobod, de ilyenkor is adj meg értelmes üzenetet.
Ez a feladat megköveteli, hogy a raise utasítással „dobj” egy ValueError-t, ha a megadott érték nem található a tömbben. A tesztek csak akkor futnak át, ha raise-elsz egy exception-t, és üzenetet is fűzöl hozzá.
Ha üzenettel együtt szeretnél ValueError-t dobni, add meg az üzenetet a exception típus argumentumaként:
# example when value is not found in the array.
raise ValueError("value not in array")
