Can I do better than binary search here?

Question

I want to select the top "range" of cards based on a percentage. I have all my two possible cards organized in an array in order of hand strength, for example:

AA, KK, AKsuited, QQ, AKoff-suit ... 

I collected 10% of the best hands, multiplying the length of the card array by a percentage that would give me the index of the last card in the array. Then I'll just make a copy of the subrange:

 Arrays.copyOfRange(cardArray, 0, 16); 

However, now I understand that this is not true, because there are more possible combinations, say, Ace King off-suit - 12 combinations (for example, an ace of one suit and a king of another suit) than there are combinations, say, a pair of aces - 6 combinations.

When I choose the top 10% of the hands, so I want it to be based on the top 10% of the hands in proportion to the total number of combinations of the two cards - 52 chose 2 = 1326.

I thought that I could have an array of integers, where each index contained the total amount of all combinations to this point (each index would correspond to a hand from the original array). So, the first few indexes of the array:

 6, 12, 16, 22 

because there are 6 combinations of AA, 6 combinations of QC, 4 combinations of AKsuited, 6 combinations of QQ.

Then I could do a binary search that runs in BigOh (log n) mode. In other words, I could multiply the total number of combinations (1326) by a percentage, look for the first index less than or equal to that number, and that would be the index of the original array that I need.

I wonder if there is a way I could do this in constant time?

Answer 1

As Groo suggested, if precalculating and memory overhead are allowed, it would be more efficient to create 6 copies of AA, 6 copies of KK, etc. and store them in a sorted array. Then you can run your original algorithm in this correctly weighted list.

This is best if the number of requests is large.

Otherwise, I do not think that you can achieve constant time for each request. This is due to the fact that requests depend on the entire frequency distribution. You cannot look only at a constant number of elements and determine whether it corresponds to the correct percentile.

Answer 2

there was a similar discussion here Algorithm for selecting files with a thumb As a comment on my answer (basically what you want to do with your list of maps), someone suggested a specific data structure, http://en.wikipedia.org/wiki / Fenwick_tree

Also, make sure your data structure will provide effective access to, say, a range of 5% to 15% (and not coding related content, though;).