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 <swetharahu...@gmail.com>wrote: > Arrays are not of the same size.... > > On Tue, Jul 19, 2011 at 10:41 PM, Rishabh Maurya > <poofiefoo...@gmail.com>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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.