Hello Venkat
One scenario that is troubling me is what if p2 is not a valid position in
l2?
findNth(start,end)
p1 = (start + end)/2
p2 = n-p1
if l1[p1] < l2[p2]:
if l1[p1 + 1] > l2[p2]:
return l2[p2]
else:
return findNth(p1+1, end)
else:
if l2[p2 + 1] > l1[p1]:
Hey Ashish check this link
http://stackoverflow.com/questions/8999610/median-of-lists
Thanks and Regards,
Venkat Gottipati
On Jan 31, 10:14 am, Ashish Goel wrote:
> i think this can be done much faster similar to findling median of two
> sorted arrays by proceeding with comparing medians of two
Use a binary search.
If you have arrays a[n] and b[m], then if you claim that a[i] is the
kth largest element, then b[k-i-2] must be larger than a[i], and b[k-
i-1] must be less (assuming arrays are zero-based). After using a
binary search to find the value of i to meet this condition, you have
to
@dave:
checkout this link:-
http://www.geeksforgeeks.org/archives/2105
algo given in this link has complexity of O(log n) .btw i have doubt if
they would work if two array are of different size.
for O(log k) ...thinking
On Tue, Jan 31, 2012 at 11:06 AM, Dave wrote:
> @Atul: Yours is an O(k) a
@Atul: Yours is an O(k) algorithm. Is there an O(log k) solution?
Dave
On Jan 30, 9:56 pm, atul anand wrote:
> to find kth largest element in the 2 sorted array can be done by simple
> merge...
> obv no need for extra space...two indexes will do.
>
> you just need to check arr1[i...n] == arr2[j.
