**Question:** There are two sorted arrays *A* and *B* of size *m* and *n* respectively. Find the median of the two sorted arrays. The overall run time complexity should be *O(log (m+n)*

### Solution

## Approach 1: Recursion

This problem can be converted to the problem of finding the *kth* element, where *k* is *(A’s length + B’ Length)/2*.

If any of the two arrays is empty, then the *kth* element is the non-empty array’s kth element.

If *k == 0*, the *kth* element is the first element of *A* or *B*.

For normal cases (all other cases), we need to recursively move the pointer at the pace of half of an array length through the following steps:

Calculate the medians

*m1*and*m2*of the input arrays*array1[]*and*array2[]*respectively.If

*m1*and*m2*both are equal then we are done, and return*m1*(or*m2*)If

*m1*>*m2*, then median is present in one of the below two subarrays:From first element of

*array1[]*to m1 (*array1[][0...m1]*)From

*m2*to last element of*array2[]*(*array2[][m2…n-1]*)If

*m2*>*m1*, then median is present in one of the below two subarrays.From

*m1*to last element of*array1[]*(*array1[][m1…n-1]*)From first element of

*array2[]*to*m2*(*array2[][0...m2]*)Repeat the above process until size of both the subarrays becomes 2.

If size of the two arrays is 2 then use below formula to get the median.

*(max(array1[][0], array2[][0]) + min(array1[][1], array2[][1]))/2*

We’re done!

*Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.*

*Subscribe to get full access to the newsletter. Never miss an update.*