We noemen een lijst \(L\) van lengte \(l\) bitonisch als er een index \(i\) (de top) bestaat, zodat:

\[\left(\forall j \in [0, i[\right)\left(L_{j} \le L_{j+1}\right)\] \[\left(\forall j \in ]i, l[\right)\left(L_{j-1} \ge L_{j}\right)\]

Anders verwoord: de lijst is een pyramide met top op index \(i\), een stijgende flank links van \(i\) en een dalende flank rechts van \(i\). Let wel op dat de top ook op de laatste of eerste positie kan liggen, en de lijst in dat geval gewoon oplopend, respectievelijk aflopend gesorteerd is.

Ontwerp en implementeer een zoekalgoritme dat gebruik maakt van de verdeel-en-heers techniek om voor een gegeven bitonische rij van \(l\) natuurlijke getallen \(L\) en een te-zoeken getal \(g\) de index van \(g\) in \(L\) teruggeeft, of \(-1\) als \(g\) niet voorkomt in \(L\). We verwachten een algoritme met tijdscomplexiteit \(O(log(l))\). Je mag er vanuit gaan dat de elementen in \(L\) uniek zijn (geen dubbels).

Implementeer de interface BitonicSearcher¹ in een klasse MyBitonicSearcher met de gevraagde methode public int bitonicSearch(Sequence numbers, int query). Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.

Net als in de vorige opgave maak je gebruik van onze Sequence klasse³ met methoden int size() en int get(int index), die hier een bitonische rij voorstelt.