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

Question

Okay. The problem comes as below:

---

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 an sorted array mered 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(logn). Any ideas?

Answer 1

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

Answer 2

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