I want to write an algorithm where given two (sorted) arrays A, B of size n,m I can find the kth smallest element in the union of A and B. Now the tricky part is the complexity has to be O(log n+logm) wish makes me think we need to find the kth element without having to merge A and B since that will be O(n+m). I also need to find a way of doing this using the divide and conquer technique smth like binary search but I don't see how one will do that. I thought of comparing the kth smallest element for each list that would work except for when there are duplicates in the arrays also it is not O(log n+logm)
Asked
Active
Viewed 16 times
