33 lines
989 B
C++
33 lines
989 B
C++
#include <algorithm>
|
|
|
|
// inputs must be random-access iterators of doubles
|
|
// Note: this function modifies the input range
|
|
template <typename Iterator>
|
|
double median(Iterator begin, Iterator end) {
|
|
// this is middle for odd-length, and "upper-middle" for even length
|
|
Iterator middle = begin + (end - begin) / 2;
|
|
|
|
// This function runs in O(n) on average, according to the standard
|
|
std::nth_element(begin, middle, end);
|
|
|
|
if ((end - begin) % 2 != 0) { // odd length
|
|
return *middle;
|
|
} else { // even length
|
|
// the "lower middle" is the max of the lower half
|
|
Iterator lower_middle = std::max_element(begin, middle);
|
|
return (*middle + *lower_middle) / 2.0;
|
|
}
|
|
}
|
|
|
|
#include <iostream>
|
|
|
|
int main() {
|
|
double a[] = {4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2};
|
|
double b[] = {4.1, 7.2, 1.7, 9.3, 4.4, 3.2};
|
|
|
|
std::cout << median(a+0, a + sizeof(a)/sizeof(a[0])) << std::endl; // 4.4
|
|
std::cout << median(b+0, b + sizeof(b)/sizeof(b[0])) << std::endl; // 4.25
|
|
|
|
return 0;
|
|
}
|