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.
Viselkedés
A megoldásodnak a tesztesetekben a Julia beépített searchsorted függvényeinek viselkedését kell mutatnia.
Ez azt jelenti, hogy ahelyett, hogy a listában talált első egyező elem indexét adnád vissza, egy tartományt adsz vissza, amelynek alsó határa a listában az első, felső határa pedig az utolsó egyező elem indexe.
A megoldásod egyszerűsítése érdekében azonban feltételezheted, hogy a keresett elem nem ismétlődik, kivéve a többszörös egyezéseket vizsgáló bónuszfeladat-tesztkészletet.
Ha a keresett elem nincs benne a listában, egy üres tartományt kell visszaadnod, amelynek alsó határa az az index, amelyre az elem a rendezett listába beszúrható lenne. Üres tartomány minden olyan tartomány, ahol a felső határ kisebb, mint az alsó határ.
A részletekért olvasd el a searchsorted függvény dokumentációját és példáit:
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.
See also: insorted, searchsortedfirst, sort, findall.
Examples
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3
julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5
julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0
Bónuszfeladatok
- Bővítsd a megoldásodat a
by, lt és rev kulcsszóargumentumok támogatásával úgy, hogy a by a lista összes elemére alkalmazott transzformációt, az lt egy összehasonlítást, a rev pedig azt adja meg, hogy a lista fordított sorrendben rendezett-e. Ha ezeket a paramétereket használod, fel kell tételezned, hogy a listát már ezekkel a paraméterekkel rendezték. A részletekért lásd a sort dokumentációját.
- Támogasd az olyan listákat, amelyekben a keresett elem ismétlődik (találd meg az első és az utolsó indexet, ahol a keresett elem egyenlőnek minősül).
