consider a sorted array with xi , xi+1, xi+2, … , xi+n distinct elements with frequencies a0,a1,a2,…,an respectively. How can i find pth element in this?
If you want to find pth element for many queries then just take cummulative frequency:
i.e,
Make an array c, such that c[i] = a[i] + a[i-1] .. ... a[0].
Now you can just perform a binary search on c to find what pth element is.
For suppose c = \{{1,5,7,8\}} and you want to find 4th element just perform binary search to find the lowest index for which c[i] \geq p which is 2 1 in this case (c[1] = 5 > 4).
1 Like
This can be done using “segment tree” if you have online queries (i.e. with update)…
Refer this answer of mine after the “view content” box…
For offline queries(without upadte) you can easily do with a binary search on “prefix sum array” of frequencies…
#maybe “fenwick tree” is also applicable here…
1 Like