sorting

Question

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

a) O(1)

b) O(logn)

c) O(n)

d) None of these

explain briefly.

Comments

first you have to merge(union) and that list also sorted ===> O(n) time.

total elements = n+n =2n ===> middle element = 2n/2 = n

with accessing nth element ===> a[n-1], you have the middle element

---

We can do in logn time . Read method 2

 

https://www.geeksforgeeks.org/median-of-two-sorted-arrays/amp/

---

thank u for correcting me @  abhishekmehta4u

Answer 1

As suggested by  abhishekmehta4u:

We can do this in O(logn) time by comparing medians of both arrays. Since both of them are of the same size, we can continuously divide the problem in half until we find medians of the same size.

More information here: 

https://www.geeksforgeeks.org/median-of-two-sorted-arrays/amp/

 

My previous less efficient answer:

It is given that you have to find the middle element of union sorted array.
So given an array of size 2n, the middle element can be found in O(1) time.
(P.S. if we have to first combine them, then it would take O(n + n) = O(n) time to combine and then O(1) time to find the middle element. So total time will be O(n) in this case)

 

Comments

We can do in logn time . Read method 2

 

https://www.geeksforgeeks.org/median-of-two-sorted-arrays/amp/

---

What is the answer???

---

the logn method.