Median of Three.md

Median Of Three

The median of three numbers is the one that has the middle value of all three. In other words, if the three numbers are sorted, the one in the middle is the median.

There are several ways of comparing operations among variable a, b and c to determine which one is the median.

One brute force way is to directly represent verify the following formula:

a <= b <= c

if (a <= b and b <= c) or (c <= b and b <= a):
   median = b

if (b <= a and a <= c) or (c <= a and a <= b):
   median = a

if (a <= c and c <= b) or (b <= c and c <= a):
   median = c

There are at most 6 comparisons in total. We can do better with some more mathematical deductions.

Below is the proof that we can reduce the amount of comparison to 3 (or less):

medianofthree.png

medianofthree.py

#!/usr/bin/env python

### MEDIAN OF THREE 

def median_of_three(a, b, c):
	"""
	Finds the median of the three elements

	@param: a: one of the three elements
	@param: b: one of the three elements
	@param: c: one of the three elements

	@return: The median of three
	"""

	#hypothesis: b is median
	# (a <= b <= c)  <=>  (a-b <= 0 and b-c <= 0)  <=>  (b-a >= 0 and c-b >= 0)
	# or
	# (c <= b <= a) <=>  (c-b <= 0 and b-a <= 0) <=>  (b-c >= 0 and a-b >=0)
	#
	# => (a-b) * (b-c) >= 0

	factor1 = a - b
	factor2 = b - c
	if (factor1 * factor2 >= 0):
		return b

	#hypothesis: a is median
	# (b <= a <= c) or (c <= a <= b) 
	# => (a-b) * (c-a) >= 0

	factor3 = c - a 
	if (factor1 * factor3 >= 0):
		return a

	#hypothesis: c is median
	# (a <= c <= b) or (b <= c <= a) 
	# => (c-a) * (b-c) >= 0

	if (factor3 * factor2 >= 0):
		return c