I am working with very interesting [problem][1]:
Given an unsorted array of n distinct elements, We want to find this set of logn elements: those at positions 1,2,4,8,16,..., n/2 in the sorted order. (The element at position 1 in the sorted order is the minimum, the one in position 2 is the 2nd smallest, ..., and the one in position n is the largest.) Assume n is a power of 2 . How fast can you find all these logn elements?
My thought process: we can find elements of any rank from an array in O(n) using the median of medians. I will not find elements in the order written above which is 1,2,4,8,16,..., n/2. I will first take the middle of asked elements (say k) which is at index (logn)/2 and then i will divide original unsorted array into two parts using two parts using k and i will work on these two parts indiviually. Using this approach i am getting loglogn levels and at each level n amount of work is to be done hence time complexity is nloglogn.
But the options given link does not have this option.
[1](page 2) https://d1b10bmlvqabco.cloudfront.net/attach/ixj45csz3f961q/grs52ylqx9y/j28yy7bo8jvm/final.pdf