There are two sorted arrays arr1[] and arr2[] of size n each, write a program to find the median of the two sorted arrays.

Problem Note

  • You have to find the median of the array formed by merging both the arrays (i.e. array of length 2*n).
  • The overall run time complexity should be O(log n).
  • You may assume arr1[] and arr2[] cannot be empty.

Example 1

Input: 
arr1[] = [1, 14, 15, 24, 35]
arr2[] = [2, 13, 19, 32, 47] 
Output: 17 
Explanation: After Merging both the array we get [1, 2, 13, 14, 15, 19, 24, 32, 35, 47]. Total number of elements are even, so we need to take average of middle two numbers which is (15+19)/2 = 17.

Example 2

Input: 
A[] = [1, 3, 5, 11, 17], 
B[] = [9, 10, 11, 13, 14] 
Output: 10.5 
Explanation: After Merging both the array we get [1, 3, 5, 9, 10, 11, 11, 13, 14, 17]. We need to take average of middle two numbers which is (10+11)/2.