Please see the image for assignment problem :- I have idea of that this will be solved by divide and conquer but can't figure out the exact way. Please suggest me some algorithm to do this. A proof is really welcome.. idea of that this will be solved by divide and conquer but can't figure out the exact way. Please suggest me some algorithm to do this. A proof is really welcome..
Part (a) is easy — For each i belongs to [1,k] you can binary search in O(logn) questions to find out how many numbers are <=i. Let this be f(i). Then print out f(i)-f(i-1) numbers equal to i. Time = O(klogn) trivially.