Binary search on two mutually exclusive arrays.

Question

There are two sorted list each of length $n$. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required using binary search is?

Their solution : $logn + logn = 2*logn = logn^{2}$.

My Solution : $min(logn_{1}, logn_{2}) = logn$ as $n1 = n2$. The intuition behind my solution is that we can do binary search in both the lists in parallel, we return from the search the moment we find the element.

 

So tell me whose solution is correct? Why my solution should be incorrect?

Comments

But how you perform parallel function call??

---

@Shubhanshu Like this. http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

---

logn

---

even if you are searching in parallel, at every iteration you are comparing 2 elements(one each from list 1 and list 2)..

total you are doing logn iterations and each iteration cost 2, therfore,

total 2*logn comparisons = O(logn)

Answer 1

Two sorted list, each of length n.

Another point is both are mutually exclusive , means every element of one list is different from every element of other list.

• So, first do binary search on list1
• if element is found then stop

         here maximum comparison will be log n

• if element not found , go to second list and find element in log n time

      So,total number of comparison O(2log n)=O(log n)

Comments

@srestha do you have any idea about parallel function call in Aghori's explanation??

---

but @ Shubhanshu

merging of 2 arrays need another array to which of size 2n.

that will more time complexity than log n

---

But our intention is to find the key in one of the two arrays and not to perform merging of two arrays.

merging of 2 arrays need another array to which of size 2n.

For merging if space is more important than time than we can use inplace merging technique of merge sort instead of outplace merging.