Find the median of two sorted arrays

By | May 24, 2014

Given two sorted arrays A and B containing N elements each. Give an algorithm to find the median of two sorted arrays in O(lgN) time.
Ex A={1,2,3} B={1,4,5,6} median=3 .

The naive algorithm will be to merge the arrays A and B and return the median .But the time complexity will be O(N) and this will require O(N) extra space .I hope you can code that solution so I’m not writing it here .But if you need that as well contactus I’ll give you that .

A Better approach is this :
We know that the median will be at Nth position when the two sorted arrays will be merged.
We can use this fact to recursively compute the Median using the following algorithm .
Algorithm:

  • Assume the Median is present in Array A.

    • Recursively search for an element in array A such that if it’s position is K in Array A then n-k-1th element in Array B should be smaller than it and n-kth element in Array B should be greater than it . It will be our median return it.
    • if there’s no such element in Array A search for it in Array B
  • Recursively search for an element in array B such that if it’s position is K in Array B then n-k-1th element in Array A should be smaller than it and n-kth element in Array A should be greater than it . It will be our median return it.

Here’s the code :

Leave a Reply

Your email address will not be published. Required fields are marked *