### Problem Statement

The statistical term median can be thought of as the "middle point" of a set of data. To determine a median, we first start with an ordered set of data. For an odd number of data points, the median is simply the middle point. For an even number of data points, the median is the average (mean) of the two middle points. Examples:

• {1, 2, 3, 5, 7} - median = 3
• {1, 2, 3, 6, 7, 8} - median = (3 + 6) / 2 = 4.5

We can think of the median of a set of data as the 1/2 way point which divides our data into a lower and upper half. When there are an odd number of data points, the median point does not belong to either set. If we take the medians of the lower and upper halves of data, we can similarly determine the 1/4 and 3/4 points within our data. (These are also known as "quartiles", see notes section for clarification.) Applying this to the two examples above:

• {1, 2, 3, 5, 7} - median = 3
• {1, 2} - 1/4 point = (1 + 2) / 2 = 1.5
• {5, 7} - 3/4 point = (5 + 7) / 2 = 6
• {1, 2, 3, 6, 7, 8} - median = (3 + 6) / 2 = 4.5
• {1, 2, 3} - 1/4 point = 2
• {6, 7, 8} - 3/4 point = 7

Similarly, we could expand upon this definition to subdivide at the 1/4 and 3/4 points, and find the 1/8, 3/8, 5/8 and 7/8 points, and so on. You are given a int[] data, your set of data points. You are also given an int numerator and an int denominator, describing the data point (as the numerator and denominator of a fraction) you need to find. Your method should return the required data point, based upon the definitions above.

### Definition

 Class: FractionPoints Method: findPoint Parameters: int[], int, int Returns: double Method signature: double findPoint(int[] data, int numerator, int denominator) (be sure your method is public)

### Notes

-Statistical definitions, particularly for quartiles, may vary depending upon the source and implementation. For this problem, we will adhere to the definition given within.
-The return value must be within 1e-9 absolute or relative error of the actual result.

### Constraints

-data will contain between 1 and 50 elements, inclusive.
-Each element of data will be between -10000 and 10000, inclusive.
-denominator will be a power of 2 between 2 and 64, inclusive.
-numerator will be an odd number between 1 and denominator-1, inclusive.
-There will be enough data points to subdivide the data to the level required.

### Examples

0)

 `{1, 2, 3, 5, 7}` `1` `2`
`Returns: 3.0`
 An example from the problem statement.
1)

 `{1, 2, 3, 6, 7, 8}` `3` `4`
`Returns: 7.0`
 Also from the problem statement.
2)

 `{7, 3, 1, 5, 2}` `1` `4`
`Returns: 1.5`
 Again from the problem statement, but provided in unsorted order.
3)

 `{7}` `1` `2`
`Returns: 7.0`
 The median of 1 point is trivial to calculate.
4)

 `{983, 126, 1078, -512, 1, 9876, -1234, 2387}` `3` `8`
`Returns: 63.5`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7565

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10718&pm=7565

timmac

#### Testers:

PabloGilberto , brett1479 , Olexiy