Gegeven een rij \(A = (a_0,\ldots,a_{n-1})\) van \(n\) verschillende gehele getallen. Een lokaal minimum in de rij is een element \(a_i\) zodanig dat \(a_i<a_{i-1}\) en \(a_i<a_{i+1}\). Grenswaarden \(a_0\) en \(a_{n-1}\) van een rij zijn lokale minima als respectievelijk \(a_0 < a_1\) en \(a_{n-1} < a_{n-2}\). Ontwerp en implementeer een algoritme dat een lokaal minimum in een gegeven rij bepaalt. De tijdscomplexiteit van je algoritme moet \(\Theta(\log n)\) zijn in het slechtste geval.

Opgave

Schrijf een Python-functie vindminimum(rij: list) die een lijst aan integers als input neemt en een lokaal minimum teruggeeft.

Voorbeelden

>>> vindminimum([12, 14, 1, 9, 20]) # ook 12 is geldig
1
>>> vindminimum([1, 5, 10, 19, 20])
1
>>> vindminimum([5,3,1,0,2,4,6,9,8]) # ook 0 is geldig
8