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 $\Theta (nlog(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.