Hi guys I need your help witb one of my tutorials here,
I have a question which says:
Let A and B be two sorted arrays of n elements each.We can easily find the kth smallest element in A in O(1) time by just outputting A[k].Similarly we can easily find the k th smallest element in B.Give an O(log k) time algorithm to find the k th smallest in the union of A and B.Prove that your algorith works.We will assume that there are no duplicate elements.
Guys I;m really confused with thsi one,I need your help.
gumedesv
0
Newbie Poster
Recommended Answers
Jump to PostThat's because it's a hard question. It was on my DSA final. Because it's an O(log k) algorithm, you can bet that it involves jumping pointers around in a binary search-esque pattern.
You might also want to try assuming that k <= n for now. (If k > n, …
All 2 Replies
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
That's because it's a hard question. It was on my DSA final. Because it's an O(log k) algorithm, you can bet that it involves jumping pointers around in a binary search-esque pattern.
You might also want to try assuming that k <= n for now. (If k > n, you can call a function that finds the 2n-k+1'th largest element.)
gumedesv
0
Newbie Poster
I'm still not sure how the assumption is going to help me.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.