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
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
{1, 2, 3, 5, 7}
1
2
Returns: 3.0
An example from the problem statement.
{1, 2, 3, 6, 7, 8}
3
4
Returns: 7.0
Also from the problem statement.
{7, 3, 1, 5, 2}
1
4
Returns: 1.5
Again from the problem statement, but provided in unsorted order.
{7}
1
2
Returns: 7.0
The median of 1 point is trivial to calculate.
{983, 126, 1078, -512, 1, 9876, -1234, 2387}
3
8
Returns: 63.5
{-9539,6291,-1823,-3507,9515,-7262,-6920,6283,-9450,2312,-740,4595,-4679,-5748,8069,3348,6257,7211,9642,-3270,-2133,-504,-5470,5093,5768,-1367,2923,-3646,4287,-3346,-7397,-3284,2492}
5
16
Returns: -3426.5
{-7019,3106,355,7399,6712,1135,8574,-6955,-1378,3912,1087,6886,7092,-5962,-8110,-8177,6171,-6341,9901,3803,965,1761,3084,725,882,-185,6725,-8004,3895,-291,-7456,-7898,8972,1793,5088,-9759,-4098,9812,-7071,5594,-708,-3550,5907}
1
16
Returns: -8110.0
{1746,5830,-7685,2397,-5169,-3569,-6943,2590,2544,-8507,1219,-9978,9629,-3483,-3103,4409,6578,-850,8912,1368,-1016,7913,-4702,-1051,-8352,5920,6359,-9271,-5694,-5490,-5486,5854,1902,-3956,9135,3984}
45
64
Returns: 3984.0
{-937,-6722,9486,-488,-3573,300,-6131,-9781,-3727,3294,6031,-8815,2714,7299,6994,-187,5695,3833,532,3366,748,-1089,71,-7673,-1717,-1966,6978,5365,-1881,3584,-2619,2913,9999,-3021,-9913,5634,1881,9472,1485,4998,-4920}
5
64
Returns: -7673.0
{-6936,-5302,-6879,1796,-2786,8859,-7911,349,-4698,-6548,-8957,8850,-9849,3206,7158,-8772,8393,3321,-1497,2099,2688,-4087,-6882,-8814,-4266,7212,-8640,7931,6222,-7653,5533,-1715,-681,9264,-2994,7629,-4838,6237,-236,6506,-3971}
11
64
Returns: -7653.0
{-540,8955,-1871,9935,-7573,4723,8244,3091,-8324,6577,-671,6958,7151,-8421,-8066,-3939,2,7498,-5842,4126,-7045,-2082,2758,-469,-9113,-3800,9528,6065,-7844,-6443,1997,-3930,-548}
3
16
Returns: -7309.0
{-7770,7605,7276,8932,-6792,7978,-745,3857,1708,9989,-7695,-145,6050,-6773,175,9761,9007,-8130,-891,9123,-8458,-3804,8598,9048,6227,5194,-7822,935,8118,-5421,-6741,-2495,3316,-2079,9704,-1544,2725,8565,-9050,6147,3699,4061,-8950,-459}
29
32
Returns: 9085.5
{-6522,2838,1980,-6205,2990,-5801,-9657,-5290,2115,6033,9007,8228,-7295,-1987,5800,8319,5738,-2872,6730,4799,6538,-1872,-6477,-8281,-2964,-9559,-9080,2961,-4576,-2520,-4854,-943,-9533,9882,1715,-660,8955,4323,1589,9060,-2838,-1395,5805,-6330,-551,4497,5860}
41
64
Returns: 2990.0
{5379,8322,3921,2810,-6219,9806,5350,-686,260,6759,2548,-6722,-2618,9286,-5365,887,-50,7760,-7178,6298,-3541,9364,-8585,5539,7670,-2363,-2068,2322,9853,2270,2538,-5419}
25
64
Returns: 260.0
{45,-843,1224,6246,6686,-9925,6364,-9975,-1305,7563,9040,5781,9780,-681,1170,2782,9499,6736,3037,6638,3887,6015,6907,8382,5140,6143,1874,-6972,-539,7990,-5780,-2033,5294,4768,-759,5477,9662,3703,-8926,-7254,9933,-3566,669}
3
16
Returns: -2033.0
{-9095,-1989,3231,2209,-7264,4702,1713,3944,447,2274,-5520,7274,3538,6032,-7830,-7469,1631,3840,-5625,-853,6796,-5273,3466,8521,6282,1518,-322,-386,-8479,-2157,7428,4548,9397,9833,9410,7627,1515,5745,597,4766,6601,-7251,-7941,-4450}
1
32
Returns: -8787.0
{1209,1497,4806,-5161,2926,-8606,3736,1456,6174,6178,4544,4709,5926,1217,-4976,-7901,2422,-7397,4846,-68,7876,3705,6622,-5458,1016,5885,-6757,-392,2546,4046,-7333,-2085,8009,-9059,-9691,8180,4807,6682,4916,6033,-9189,-2059,-6342,-6768,-6918,6805}
31
32
Returns: 8094.5
{-258,4501,326,9455,704,580,7465,7503,4875,264,3823,7041,8151,-5872,8909,-7872,3510,-3372,6700,4985,908,-3157,-2708,5740,-2313,8813,-880,-66,47,3389,-8541,4210,6066,-6136,9866,8044,-6280,-6789,7211,-2571,-6525,-7195,-6695,-5457,-7141,7875,7881,6683,-969,-8470}
31
64
Returns: 580.0
{-9895,-5166,-1530,-7102,-2791,4586,1768,1891,-8541,-2470,-2544,-8515,-1196,9612,-9026,4287,-5738,-9136,8407,298,-583,-729,1509,-1898,-6462,-7252,2880,-188,-9069,2436,-9097,-1483,-6332,-4995,4105,1231,5393,6967,835,-867,1443,-4680,-4031,5945,5349,-8181,5739}
11
64
Returns: -8181.0
{-6406,2421,-1833,-6878,9423,-2964,833,3324,-9633,9359,-5540,-8295,-8044,959,-977,-3373,8938,7817,-6202,-4493,-257,8893,-2706,29,-726,8855,-5904,-6698,5564,2753,-8281,-2991,-366,2911,7337,-9985,2735,-4606,-5756,7969,-6729,7906,5025,7607,-3625,-2572,-513,4360}
53
64
Returns: 7607.0
{6410,-5999,1940,7738,-2843,-5300,-4874,8138,3848,-9433,-7061,-2469,7760,-2386,7640,7450,2071,-956,3621,-993,3891,3544,3572,-4172,-7764,1836,-6132,-313,-6347,-8154,-633,-264,-3644,-3754,6342,7718,5068,1895,-4246,2636}
47
64
Returns: 3848.0
{1546,-6323,5029,5739,-9854,-2590,9967,-1076,5356,-9558,-9262,-2062,5426,-7134,428,-3889,5502,5321,-9168,5439,4484,2001,1200,3203,-8825,1514,1272,9921,-7619,-9825,-6710,-9015,4119,9293,-8003,-105,799,-3504,1689,6457,-281,4728,-3511,-1076,-1003}
29
32
Returns: 6098.0
{3475,-2710,-1044,6392,432,1804,9448,-9887,9544,2476,-8175,4564,-1368,6138,-9955,-3457,5180,7152,9753,3818,6132,-9132,-9468,5312,-994,-6369,-5625,-4280,9755,-4488,-7725,-5794,-7244,-9306,7796,2630,3424,-6217,2857,-820,4671,9180}
1
8
Returns: -8653.5
{-1027,1931,-6943,-9682,-326,-1815,1308,1772,-757,-5401,4687,2607,-3242,3644,-2614,-3199,-2571,3728,-9643,4032,201,7619,1808,-2062,8342,-2586,3118,1397,-5706,573,9147,6951,8416,-6887,-3662,7074,-9426,-5944,6046,1569,4204,502,4963,8156,-3994,-4811,-4128,9780}
51
64
Returns: 4963.0
{-8249,-9058,8823,-1580,-2783,1354,-9877,5118,-8025,-7741,5067,9910,-2523,8670,-4548,7735,4191,-6355,-2695,311,-3774,-6628,7682,-1213,9827,9698,-7345,3651,-8069,3153,-8458,3337,5000,8238,-1179,8204,8128}
31
64
Returns: -1179.0
{4983,6951,-4545,-7920,3786,6502,4293,-6975,6293,2704,-1730,998,-7773,2474,-3915,9829,8378,-6740,35,-1408,-2482,-1301,-3528,3186,-1178,-9283,-8271,-5090,-761,-152,-2753,9607,-5805,-2251,2321,3360,-9229,-8709,-6105,2285,-4466,6673,-3638,-9054,3661,-7845,9315}
3
64
Returns: -9229.0
{8408,443,4944,-1908,-8598,-1624,-3716,479,2268,3257,3069,4772,-617,3785,-3555,-4544,-1337,-3198,4477,-9848,2725,9058,7086,9364,7750,-6942,845,-7664,-4475,9525,-3333,-8598,-9134,5994,831,9405,2303,1515,-7207,9372}
19
64
Returns: -3333.0
{-1498,-1966,826,7513,6151,-7113,9917,5489,-5002,5352,-5163,-9290,6190,9349,3356,5579,341,8343,7531,-6053,-5047,2742,-3410,1667,3905,3388,-7046,-2961,3153,7147,-5992,5104,4115,-156}
33
64
Returns: 3153.0
{-1462,-9763,-3093,-2043,-7581,35,4527,1315,6564,-9844,9804,1481,-3952,6723,-8827,-5550,-8159,-7911,7926,5759,-8557,9159,-6393,-7238,9933,2877,-7664,-2150,1343,-267,-3406,-3655,-1207,-5697,-2959,104,1436,-427,-8473,4918}
57
64
Returns: 6723.0
{5102,3748,3583,1472,-9010,6429,5974,9558,3262,2026,1917,4796,-2392,-621,6629,-5856,-1976,-458,-2301,-3323,9971,-3169,3562,3458,-7312,-8255,-318,1068,3013,2267,-9439,-6992,7544,-3832,-5944,-141,-821,-1540,1886,-4094,1875,1785,6470,4567,4428,3996}
13
16
Returns: 4796.0
{3475,-2709,-8451,1985,-2782,1537,5303,-1729,-9814,-9876,-1216,9245,-3253,-5094,-3456,-9005,1465,-1091,7252,-8560,-4677,-3230,4965,9563,7656,-8208,4801,-1815,360,8995,9030,-1308,-4950,2020,7593,-4278,717,-1425,5789,-3994,864,5784,-327,-946,9676,2640,9158,-3031}
17
64
Returns: -3253.0
{-6899,-4481,6743,5254,2339,-3296,2326,-8014,4328,-4575,6735,-2882,7910,-8810,-8906,-9908,4194,4727,-2688,-9178,277,-7111,3119,1245,575,-462,7097,-4089,9887,-4985,-7366,-2168,-7055,4885,5893,3511,1948,-204,9681,888,3395,-1269,4247,363,-730,-6254}
7
8
Returns: 6735.0
{-2041,9583,8446,-5569,9656,-5583,-4802,-9789,2399,-4503,-5322,-7200,-393,-3586,-7902,-687,-7209,-1097,-5828,-6975,-4703,-2418,-1856,-5602,5046,6424,-2574,-8455,-1358,-7245,-8025,-3172,1664,-1386,7951,-9697,-3431,8202,-1824,8527}
31
64
Returns: -3172.0
{-8889,-3550,-4883,6880,-8720,-3019,-3368,-5067,-2429,-9633,9574,4848,-6816,-9623,1439,4047,-616,-6769,6990,-6348,1569,-356,-6478,7850,1136,-9008,-1537,-8205,-7257,-5411,-9274,-4356,3337,-384,-3530,-8306,9281,8165,5143,-9555,4913,-6292,5183,-8393,-2746,6815}
17
64
Returns: -6769.0
{-1136,2521,-1183,-5056,-8463,-3965,-5888,1467,-7073,-2733,-4256,-9713,8517,-5163,-7811,-7018,9640,3929,-8490,3568,3906,-255,4766,1219,-1912,6544,-1262,-2140,4460,-8086,595,4320,5562,889,2930,222,5771,5782,-5893,-2698,-4496,5003,8766,2013,2421,4856,-8072,75}
5
64
Returns: -8086.0
{-8033,3325,5305,1861,-6333,9119,7754,7598,6856,-5008,7296,6251,7007,-8988,6671,1424,-5275,-2372,1907,1967,-2790,-6142,-178,4207,-1936,8903,978,-7248,8797,3231,4616,8663,-3658,-7741,9947,7270,9014,-6300,-2779,3811,2467,8172,8925}
15
16
Returns: 9014.0
{-748,7996,7753,5342,-9003,131,4299,8168,-449,-5010,8108,-6498,-8903,-6203,-5236,-1860,5002,8801,-6376,376,8632,-92,4747,-8935,9401,2409,-8976,-9594,8095,9499,-963,-5067,707,-5799,8811,-9094,3224,-2590,7800,-6900,-9684}
1
32
Returns: -9639.0
{7268,-8161,3767,7917,9903,-7543,-4330,7465,9371,5300,-1262,1373,9343,-6752,6688,5941,-1413,-894,3893,-9928,51,5952,3175,2795,6896,-5015,-6143,4915,-2409,-9000,-9477,59,8138,3117,7479,9225,-4367,4492,-8880,7949,2425,-7966,-334,-368,-8031,2827,9467}
55
64
Returns: 7949.0
{1469,-788,3993,-3578,-9579,-3261,-8685,-1336,-9029,-8979,4917,8599,754,-127,8370,4777,8678,3235,-3774,-4232,7462,307,4095,-2014,5944,-2353,-1983,-3714,-6457,826,-5932,-4482,-3801,8379,6122,1788,-3470,-6363,7716,-3622,6163,561,-5338,3471,-3797,9349,-8329}
19
32
Returns: 790.0
{4855,-6710,9592,3241,1889,9074,-8838,5116,-3993,478,2774,8722,5029,-4879,145,6952,-601,2400,2375,3751,-3418,-1754,5041,5518,9847,-395,-3100,-4355,-9376,-8217,6595,-4024,5857,4990,-1312,-2465,-5525,2276,4309,9305,4960,6671}
1
32
Returns: -9107.0
{-5059,-2345,-8867,-4560,4516,6518,6803,-3052,-705,8408,-5287,-3392,-1751,-5926,3393,-7716,2173,5517,4492,-5776,3883,-3202,-7135,-9962,6432,-7391,2477,7123,8091,3070,8790,-90,-2276,-8118,576,2192,-1529,-8540,1128,-5895,-5021,-353,6680,7448}
1
2
Returns: -529.0
{9286,-9599,8882,2025,-2869,9443,-7821,6298,9275,8143,-5210,-8905,-993,1906,-5959,9680,-1144,6225,9617,4802,8883,-3634,3497,-8799,3812,713,-5612,386,9244,-5764,117,-4584,-240}
45
64
Returns: 6298.0
{2075,8240,-3934,-4062,9347,-2269,1426,-7393,2433,-2599,-2624,2452,9221,-9936,-4701,-9210,-9545,7830,5475,-6804,2920,-3096,7681,8212,6418,5054,1792,7053,5039,-1975,9374,1334,4654,-1417,1965}
5
64
Returns: -9210.0
{287,-9730,-2929,-2543,-6242,-8937,3800,-3564,8260,-4834,322,3945,-6555,-338,-2414,4285,1156,403,-4829,-9441,-2147,-481,-5708,5939,4373,-2432,-5593,-1974,6041,7797,638,-1902,-6141,7999}
1
2
Returns: -1938.0
{-1597,5738,-839,-4160,-6120,1776,8158,-112,-8531,-6892,1593,8362,1788,7048,-6503,8179,-3206,-9120,4937,-9233,5977,1131,3084,6190,6655,-4227,394,-9537,4527,-7777,85,-4555,9494,25,-4119,5418,-8758,9330,6678,6076,1361,4404,4469,1264,5974,-3956,6238,8992}
45
64
Returns: 5738.0
{-8696,-7021,-6938,-600,-8418,7271,-7346,2970,-816,8107,-8618,7695,5360,9245,3022,-3852,8868,-8238,1166,-1921,6937,-2537,-5798,8861,-594,-8428,6662,-8181,-9784,611,-466,1401,-3837,-7932,-9081,-2894,-7617,94,-1558,-1391,2764,-1728,146}
29
32
Returns: 7901.0
{3665,9043,5224,8241,-175,-2824,4476,-2174,-3780,5521,3840,8776,-5799,9993,-9990,-9391,-9166,2753,8573,-1428,-19,1531,3291,8325,-4084,-6236,-1227,3319,-7444,5315,-1335,7317,-4369,-5833,5740,-7472,-8562,-6423,390,-6566,5058,-6425,9943,-3454,-2921}
13
32
Returns: -2499.0
{100,-1568,-2000,1929,5518,1572,-3,-5288,-7867,-4248,6898,2325,-3940,8402,-8844,-4731,904,-3144,6522,3144,-9966,-5748,7481,9171,7256,-7638,5138,3514,-3595,1588,-3255,1246,7586,-4418,8673,-5113,4556,-6615,3146,-4255,5634,9454,3606,6776,-5461,1252,-5671,-4968,3902}
57
64
Returns: 7481.0
{9689,557,5185,8147,-4153,951,-1172,4673,3156,6433,6483,8307,545,9006,-4348,4738,-9522,9729,6269,712,-2481,3710,777,7510,-9421,645,-9296,4631,-3996,8032,106,9612,-1901,-7451,-2945,-9312,-7599,-2565,2825,3935}
9
32
Returns: -2523.0
{9989,-689,9150,-8853,-6939,7769,8887,6514,-6149,-4698,7632,-2407,-8481,-4021,9779,7674,7568,5201,247,4197,-1332,5123,-3673,6870,207,-2005,1951,-5037,2336,3043,-3097,-7667,-5016,8807,3721,-8534,8359,9432,-2416,-7066}
49
64
Returns: 7632.0
{4180,-5196,-8021,-9495,-8970,-8924,-9091,-5273,-134,7623,-6312,1530,-9957,-5135,-7017,-7721,939,5066,-4182,3923,-5823,808,8398,5299,-7391,-7289,2258,8313,9315,8135,-2383,-2688,8453,9178,-9057,-8477,4891,-298,-3036,875,-5946}
3
8
Returns: -5548.0
{-720,8644,3454,8763,-1145,8482,6080,-1507,2517,7116,-8180,-4688,-6629,-3595,-3321,7896,8318,-1182,-7405,-4589,1731,5,6375,3077,-9136,-6078,-8540,-2612,-8763,-1899,4942,-131,6567,-2368,-882}
13
16
Returns: 6841.5
{-6053,-6598,9831,-6765,-358,5100,196,6633,3865,7571,5118,-1789,1805,-1355,-7943,-8542,-7803,1444,9274,-7731,-9623,7899,-5068,7021,-1309,-2744,-5585,-7827,1950,-1256,5739,7286,25,-1259,4371,-4585,-7236,-7824,-7911,4905}
5
16
Returns: -5585.0
{-3001,-3649,-3658,9176,-569,9456,2884,-1590,4370,6188,-157,4385,-1223,-3952,8470,-7191,4543,-7615,684,-1978,-5318,-4880,-8168,7831,8186,-6936,4274,6642,8694,-9980,-645,-5631,6090,-6067,899,8581,678,-485,7825,-5041,-712,-6461,4374,9551,-2557,5639,9964}
13
32
Returns: -967.5
{9954,-2367,9703,-5779,8156,1761,-8122,-5481,-1489,-9011,-3633,-4819,6242,-284,4349,-3167,-4526,8294,-5157,5149,9888,2130,-4973,-5440,-4276,8734,-8858,746,-7720,388,-7454,-6901,-4048,-304,8739,2386,-349,-9852}
7
8
Returns: 8734.0
{1, 2, 3, 4, 5 }
3
4
Returns: 4.5
{-1, -2, -3, -4, -5, -6, -7, -8, 9, 10, 11, 12, 13, 14 }
5
8
Returns: 9.0
{-1, -2, -3, -4, -5, -6, -7, -8, 9, 10, 11, 12, 13, 14, 21, 36, 28, 30, 32, 51, 66 }
7
16
Returns: 9.5
{-7940, 910, 9164, 6998, -126, 7132, 4678, -4167, 1910, -9990, -3114, 4124, -5154, -7517, -6320, -5840, 95, 8152, 8408, 3978, 1529, -1698, -7963, -7336, 9818, -7550, 7344, 6029, 2620, -5846, -6490, -5574, -8597, -5463, -3879, -2075, 4824, -2909, -478, -5500, 4454, -7468, 5035, 2747, 6725, 1440, 860, 5375, -2663, 8036 }
31
64
Returns: -126.0
{-2314, 345, 2, 45, 3, 456, 12, 2, 324, 453, -12, 3, -23, 1, -10, -423, -564, -5345, -456, -4, -76, -756 }
13
16
Returns: 184.5
{-123, -423, -54, -312, -34, -312, -534, -534, -56, -43, -56, -43, 0, 43, -65, 32, 45, 65, -65, -43, 645, 76, 23, -534, -432, -43, -534, -423, 34, 564, 43, 43 }
57
64
Returns: 65.0