Find number of indices i such that a[i] < x.

You are given an array a containing n distinct integers. You are also given multiple integers xi. For each xi, you need to find number of indices i such that a[i] < x. You are allowed to do pre-computation of O(nlogn), but for each i, you should be able to answer in O(logn). You are not allowed to use sorting.

1Comment
shivani @shivani1234
11 Aug 2017 11:57 am
This question can be solved by using heap concept. Since , we are allowed pre computation of O(nlgn) then we can do min heapify with the modification that we use flag swap to see if there was any swapping , if there was no swapping then we count no. of such elements as indices and return for every a[i].