#Divide and conquer

Question

Given 2 sorted arrays each of n-elements and distinct. How much time it will take to find middle element of union array?

(a) O(1)

(b) O(log n)

(c) O(n)

(d) None of these

Comments

Binary search on both the arrays, rejecting half-half elements alternatively from each array.

O($\log n$)

---

We have to find middle of union array, then why we don't do union of both arrays first then find middle?

---

Agree with @Debashish Deka...you can refer https://www.geeksforgeeks.org/median-of-two-sorted-arrays/

---

There is a difference between middle element and median element. And, secondly it is not given in the question that the arrays are sorted, then how can you apply binary search?

---

@rajatmyname : Question starts from "Given 2 sorted arrays"...

---

But in this question it is asking to find middle element not median.

---

similar problem and solution

Answer 1

Check Method 2 here : http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

Comments

How you can apply binary search on the union array since it is not mentioned that union array formed is sorted?

---

does union need to be sorted? and when to apply binary search. That method in geeks for geeks if want to find mid element how can we modify last stage with 4 elements.Because if union is not sorted then finding a middle element can be done constant time.

If union needs to be sorted then it can be done in O(n) time like in merge sort and we can find mid in constant time. This one method.

but I didn't understand binary search method. Please provide a little detail explanation.

---

after the union does the resultant array needs to be sorted ? Didnot get the question .

Answer 2

Answer would be O(nlgn)

In order to find middle of union array atleast half of both the arrays should be compared and we can do this by using binary search on both the arrays, so three cases arrives,

1) both m/2 and n/2 array are covered then we will find the middle element (or)

2) array 1 is totally over (or)

3) array 2nd is totally over

 

In all these three cases binary search will take O(nlgn)

Answer 3

@arjun , @bala sir can you please check ...i think answer should be O(n) as it will take O(n+n) time (merge procedure) to create 1 sorted array and then O(1 ) to get middle element.....

and O(log n) is not right? and if not why?

Comments

@crazysarth For finding the middle element, we do not need to merge the array. We can simply check for the median of the union by using method 2 here, where we find the median of both the arrays and by comparing them try to find the median of union of both the arrays lies.  https://www.geeksforgeeks.org/median-of-two-sorted-arrays/  

This way we can do it in O(log n) time. The approach which you suggested (I thought the same earlier as well) would take O(n) time. 

Answer 4

It will take O(n)  because you have to first find the union of both both array is sorted than we can find union by merge algorithm and you know merge algorithm take O(n) time after that middle element n/2 constant time O(1) overall it will take O(n) time

Answer 5

Edit 1: This question is a duplicate of https://gateoverflow.in/227458/sorting?fbclid=IwAR1GJNWosv560XE1VFqji7KAwgPoVjLXgZuKF0CLfMPDGDR2J6PsTYYjPcs 

Edit 2: For getting the median/middle efficiently we don't have to necessarily perform the union or merge operation. The method 2 shown here https://www.geeksforgeeks.org/median-of-two-sorted-arrays/ works better than finding the union first and finding the median. So it can be done in O(log n ) time.

 

 

 

 

Why not O(n)? 

The question is asking for the middle element of the union of 2 sorted arrays. By "middle" I am assuming that it wants the value at the middle index, please correct me if I am wrong here. I did not see anything in the question that makes me search for the median as others have suggested. 

Consider 

A[] = {1,3,4,5,7}
B[] = {2,3,5,6,8}

Both the sorted arrays are specified as given. Both have equal length and distinct elements in each. 

Now the Union array would be 

U[] = {1,2,3,4,5,6,7,8}

Which would take O(n+n) time. 

Now, middle of U[] can be found out by

int mid = firstIndex + (lastIndex-firstIndex)/2

which would take O(1) time, and so total time would be O(n).