A list L with length l is called bitonic if there exists an index i where

\[(∀j∈[0,i[)(L_j≤L_{j+1})\] \[(∀j∈]i,l[)(L_{j−1}≥L_j)\]

Or in other words: the list is a pyramid with the summit on index i, a rising edge to the left of i and a descending edge to the right of i.

The summit can be the first or the last position, in that case, the list is simply sorted, or reversed sorted.

Create an search-algorithm search_bitonic(g,L) using the divide-and-conquer technique to search a number g in a given list of natural numbers L. If L does not contain g, -1 is to be returned. We expect an algorithm of timecomplexity O(log(l)). L does not contain any dubbels.

Example:

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