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 Python-functie vindKdeKleinste(k:int,rij1:list,rij2:list) die het k-de kleinste element van de unie van rij1 en rij2 teruggeeft.
>>> vindKdeKleinste(7,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
7
>>> vindKdeKleinste(8,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
8
>>> vindKdeKleinste(1,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
1
>>> vindKdeKleinste(2,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
2
>>> vindKdeKleinste(25,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
25
>>> vindKdeKleinste(24,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
24
>>> vindKdeKleinste(23,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
23
>>> vindKdeKleinste(19,[1,2,4,6,8,9,10,11,12,15,16,18,19],[3,5,7,13,14,17,20,21,22,23,24,25])
19
>>> vindKdeKleinste(5,[],[3,5,7,13,14,17,20,21,22,23,24,25])
14