Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by dogruck on Friday October 20, 2017 @04:15AM
(#15514275)
Confusing because the problem statement says you cannot assume anything about the data structure storing each set. To me, that implies it must be treated as a stream -- not an array with indexing.
But yeah, if they are arrays, you use binary search. Not obvious, but also straightforward if you are looking to beat O(k).
But yeah, if they are arrays, you use binary search. Not obvious, but also straightforward if you are looking to beat O(k).