Een circulair verschoven rij is een gesorteerde rij met \(n\) verschillende gehele getallen die circulair verschoven is over \(k\) posities.

• (35, 42, 5, 15, 27, 29) is een gesorteerde rij die verschoven is over \(k=2\) posities.
• (27, 29, 35, 42, 5, 15) is een gesorteerde rij die verschoven is over \(k=4\) posities.

Wanneer de waarde van \(k\) gekend is, dan kan het grootste getal uit de rij gemakkelijk worden bepaald in \(\Theta(1)\) tijd. Veronderstel nu dat de waarde van \(k\) niet gegeven is. Ontwerp en implementeer een \(\Theta(\log n)\) algoritme dat het grootste getal uit de rij bepaalt.

Opgave

Schrijf een Python-functie bepaal_maximum(rij: list). Als input neemt deze methode een circulair verschoven rij en als output geeft deze het maximale element van deze rij terug.

Voorbeelden

>>> bepaal_maximum([5, 6, 1, 2, 3, 4])
6
>>> bepaal_maximum([5, 1, 2, 3, 4])
5
>>> bepaal_maximum([1, 2, 3, 4])
4
>>> bepaal_maximum([3, 1, 2])
3
>>> bepaal_maximum([2, 1])
2
>>> bepaal_maximum([1])
1