Een meerderheidselement in een rij van lengte \(n\) is een element dat meer dan \(n/2\) keer voorkomt. Merk op dat er dus hoogstens één dergelijk element is. Bijvoorbeeld, de rij

[3, 3, 4, 2, 4, 4, 2, 4, 4]

heeft een meerderheidselement, namelijk 4. Anderzijds heeft de rij

[3, 3, 4, 2, 4, 4, 2, 4]

geen meerderheidselement. Ontwerp en implementeer een \(Θ(n \, log(n))\) algoritme dat gebruik maakt van de verdeel-en-heers techniek (zonder te sorteren) om voor een gegeven rij van natuurlijke getallen het meerderheidselement te bepalen, indien het bestaat.

Implementeer hiervoor de interface Majority¹ in een klasse MyMajority. De gevraagde methode public int findMajority(Sequence numbers) geeft het meerderheidselement terug van de gegeven reeks natuurlijke getallen, of -1 indien er geen meerderheidselement is. Aan een reeks van de klasse Sequence² kan je de grootte opvragen via size() en het element op een bepaalde index \(i\) via get(i). Analoog naar List#subList³ kan je in constante tijd een subreeks maken met subSequence(from, to).

Gebruik eventueel de testklasse SimpleTest⁴ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.