C++: Median

Write a program to find the median value of a vector of floating-point numbers. The program need not handle the case where the vector is empty, but musthandle the case where there are an even number of elements. In that case, return the average of the two middle values.

There are several approaches to this. One is to sort the elements, and then pick the one(s) in the middle. Sorting would take at least O(n logn). Another would be to build a priority queue from the elements, and then extract half of the elements to get to the middle one(s). This would also take O(n logn). The best solution is to use the selection algorithm to find the median in O(n) time.

#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;
}