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?
@Shubhanshu Like this. http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
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.
here maximum comparison will be log n
So,total number of comparison O(2log n)=O(log n)
@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.
For merging if space is more important than time than we can use inplace merging technique of merge sort instead of outplace merging.
64.3k questions
77.9k answers
244k comments
80.0k users