A national quiz reports each candidate's percentile rank: the percentage of the whole cohort that the candidate did better than, where a candidate with exactly the same score counts as half better and half worse. For a query score x in a cohort of n scores:
rank(x) = 100 * (number of scores below x + 0.5 * number of scores equal to x) / n
The query does not have to be one of the cohort's scores.
Write percentile_ranks(cohort, queries) that returns the list of rank(x) for every x in queries, in order, as floats. The cohort can be large and there can be as many queries as cohort members, so looking through the whole cohort for every query is too slow.
Examples
Input: cohort = [12, 15, 15, 18, 20], queries = [15, 20, 10, 16, 25]
Output: [40.0, 90.0, 0.0, 60.0, 100.0]
Explanation: for 15, one score is below and two are equal: 100 * (1 + 1) / 5 = 40.
For 20, four are below and one equal: 100 * 4.5 / 5 = 90. Nobody scored below 10,
three scored below 16, and everyone scored below 25.
Constraints
1 <= len(cohort) <= 10**5,0 <= len(queries) <= 10**5- scores and queries are whole numbers from 0 to 10**6
- floats are compared with a tolerance of
1e-6
Goals
- Compute the percentile rank of a score with a stated treatment of ties
- Answer many rank queries quickly from one sorted copy of the data
- Count the values below and equal to a query with binary search