We noemen een lijst \(L\) van lengte \(n\) bitonisch als er een index \(i\) (de top) bestaat, zodat \((∀j∈[0,i[)(L_j≤L_{j+1})\) \((∀j∈]i,l[)(L_{j−1}≥L_j)\)

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 zoek_bitonic(g,L) dat gebruik maakt van de verdeel-en-heers techniek om voor een gegeven bitonische rij \(L\) van \(n\) natuurlijke getallen 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 \(\Theta(\log(n))\). Je mag er vanuit gaan dat de elementen in \(L\) uniek zijn (geen dubbels).

Voorbeeld:

>>> zoek_bitonic(7,[2, 5, 7, 8, 19, 18, 12, 9, 3, 1])
2
>>> zoek_bitonic(4,[2, 5, 7, 8, 19, 18, 12, 9, 3, 1])
-1
>>> zoek_bitonic(6,[0, 14, 17, 19, 16, 15, 12, 6, 5, 2])
7
>>> zoek_bitonic(4,[0, 2, 3, 4, 7, 9, 13, 14, 16])
3
>>> zoek_bitonic(18,[18, 15, 12, 11, 9, 1, 0])
0