Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

algorithm

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 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?

like image 888
SiLent SoNG Avatar asked Jul 30 '10 07:07

SiLent SoNG


1 Answers

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

like image 165
Anurag Avatar answered Nov 09 '22 11:11

Anurag