News for hackers. Stuff that matters.
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col... by szemet on Friday October 20, 2017 @05:07AM (#15514451)
If the data structures can be split (as it seems), then the first step should be to get the head k element of both collections, so we only have to work with a maximum of 2k elements. Then the solution is not O(2 * log(N)) but O(2 * log(min(N,2k))).
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col... by jacksontale on Friday October 20, 2017 @05:33AM (#15514562)
Good thought, and also if k < N / 2
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col... by jacksontale on Friday October 20, 2017 @06:02AM (#15514639)
Edited the post and added your comment