i found an algo in log(k) but necessary condition is that k must be less
than both the size of arrays...
now it works like that
we will find using binary search applying on both the arrays
assume both the arrays upto k-1 positions only because the number lies in
between only
now consider two arrays as arr1[] and arr2[]
first compare arr1[k-1] with arr2[0]... if arr2[0]>arr1[k-1] then arr1[k-1]
is the solution and similarly for arr2[k-1] and arr1[0] also
if not then apply the algo
let i=(k-1)/2; // initial
compare arr1[i]and arr2[i]....let arr1[i]>arr2[i] //vice versa can be also
A. if arr1[i+1]<arr2[i-1] and arr1[i-1]<arr2[i+1]
then if k%2(mean odd no) then smaller i.e. arr2[i] is our solution
else(k is even) arr1[i] is the solution
else
move position of i as for smaller arr2[] as i+= (k-1-i)/2 and for
arr1[] j-=i(new value just calculated in this line before) //simple binary
search approach
repeat untill we find the solution... :) :)
taking an example with k=8;
arr1[]= {1,3,5,7,9,11,13,15...............}; //no need for rest of
elements as they are sorted
arr2[]={12,14,16,18,20,21,22,23.........};
now neither 15<12 nor 23<1
so first i=3
so compare arr1[3] and arr2[3] as 7<18 now 9 is not greater than 18
(hence no need to compare 14 and 7)
now compare arr1[5] and arr2[1] as 11<14 now 13 in not greater than 14 so
next step
now compare arr1[6] and arr2[0] as 13>12 now 11<12 and 14>13 so both
conditions met now 8 is even so our solution is 13
i hope this is useful :) :) :) :)
On Tue, Jul 19, 2011 at 10:58 PM, swetha rahul <[email protected]>wrote:
> Arrays are not of the same size....
>
> On Tue, Jul 19, 2011 at 10:41 PM, Rishabh Maurya
> <[email protected]>wrote:
>
>> Its solvable using Binary Search , offcourse not in log(k) but in log(sum
>> of size of array).
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
