Find the middle element in merged arrays in O(logn)

We have two sorted arrays of the same size n. Let's call the array a and b.

How to find the middle element in开发者_C百科 an sorted array merged by a and b?

Example:

n = 4
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

merged = [1, 2, 3, 3, 4, 4, 5, 6]
mid_element = merged[(0 + merged.length - 1) / 2] = merged[3] = 3

More complicated cases:

Case 1:

a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

Case 2:

a = [1, 2, 3, 4, 8]
b = [3, 4, 5, 6, 7]

Case 3:

a = [1, 2, 3, 4, 8]
b = [0, 4, 5, 6, 7]

Case 4:

a = [1, 3, 5, 7]
b = [2, 4, 6, 8]

Time required: O(log n). Any ideas?

Look at the middle of both the arrays. Let's say one value is smaller and the other is bigger.

Discard the lower half of the array with the smaller value. Discard the upper half of the array with the higher value. Now we are left with half of what we started with.

Rinse and repeat until only one element is left in each array. Return the smaller of those two.

If the two middle values are the same, then pick arbitrarily.

Credits: Bill Li's blog

Quite interesting task. I'm not sure about O(logn), but solution O((logn)^2) is obvious for me. If you know position of some element in first array then you can find how many elements are smaller in both arrays then this value (you know already how many smaller elements are in first array and you can find count of smaller elements in second array using binary search - so just sum up this two numbers). So if you know that number of smaller elements in both arrays is less than N, you should look in to the upper half in first array, otherwise you should move to the lower half. So you will get general binary search with internal binary search. Overall complexity will be O((logn)^2)

Note: if you will not find median in first array then start initial search in the second array. This will not have impact on complexity

So, having n = 4 and a = [1, 2, 3, 4] and b = [3, 4, 5, 6]

You know the k-th position in result array in advance based on n, which is equal to n. The result n-th element could be in first array or second. Let's first assume that element is in first array then do binary search taking middle element from [l,r], at the beginning l = 0, r = 3; So taking middle element you know how many elements in the same array smaller, which is middle - 1. Knowing that middle-1 element is less and knowing you need n-th element you may have [n - (middle-1)]th element from second array to be smaller, greater. If that's greater and previos element is smaller that it's what you need, if it's greater and previous is also greater we need to L = middle, if it's smaller r = middle. Than do the same for the second array in case you did not find solution for first. In total log(n) + log(n)