#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

@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

In question it's written to find middle element not median.

---

Yes. So the answer should be O(n).

---

why O(n)

we r doing binary search, will take O(log n)

---

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