Gegeven is een rij van \(n\) natuurlijke getallen. Een meerderheidselement is een element dat meer dan \(n/2\) keer voorkomt in de rij. Ontwerp en implementeer een verdeel-en-heers-algoritme dat bepaalt of een gegeven rij een meerderheidselement bevat, zonder de rij te sorteren of een dictionary te gebruiken.

Opgave

Schrijf een functie meerderheid die een lijst als parameter krijgt en die de waarde van het meerderheidselement teruggeeft als de lijst een meerderheidselement bevat; anders geeft de functie de waarde \(-1\) terug.

Voorbeelden

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