CODEWITHSUNDEEP
arraysalgorithmsortingmergesortselection-sort
Gaurav Anand
Gaurav Anand

Reputation: 90

Given two arrays each containing n sorted elements, is there a O(log n)-time algorithm to find the medians of all 2n elements?

O(n) approach is to merge the two lists and then averaging the middle two elements. But can it be optimised further ? Is there a O(log n) solution to the problem?

Upvotes: 2

Views: 128

Answers (1)

Malcolm McLean
Malcolm McLean

Reputation: 6404

You can do it in O(log n)^2 time with a nested binary search. Your two guesses for the median and highest element and lowest element (which you can get in two comparisons). Then take the mid. Then find the indices of the mid with two binary searches. That tell you whether your estimate is too high or too low, and iterate the outer binary search.

Upvotes: 2

Related Questions