Gegeven zijn twee gesorteerde lijsten van lengte \(m\) en \(n\). Je mag veronderstellen dat alle elementen in de lijsten verschillend zijn. Gevraagd wordt het \(k\)-de kleinste element in de unie van de twee lijsten te bepalen.
Ontwerp en implementeer een algoritme met tijdscomplexiteit \(\Theta(\log m + \log n)\) voor dit probleem.
Schrijf een klasse KdeKleinsteElementBepalen die de interface ElementBepalen1 implementeerd.
Deze interface bevat de methode int kdeKleinsteElement(Integer[] rij1, Integer[] rij2, int k) die, gegeven 2 lijsten, het k’de kleinste element van die 2 lijsten teruggeeft.
k begint van 1 te tellen.
Het allerkleinste element zoeken van de lijsten n en m zou dus
kdeKleinsteElement(n, m, 1) zijn.
Gebruik eventueel de testklasse SimpleTest2 om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.