Median Value

The Median is the "middle number" (in a sorted list of numbers).

How to Find the Median Value

To find the Median, place the numbers you are given in value order and find the middle number.

(Note that it didn't matter if we had some numbers the same in the list)

Two Numbers in the Middle

BUT, if there are an even amount of numbers things are slightly different.

In that case we need to find the middle pair of numbers, and then find the value that would be half way between them. This is easily done by adding them together and dividing by two.

(Note that 22 was not in the list of numbers ... but that is OK, because half the numbers in the list are less, and half the numbers are greater.)

The Median is the "middle number" (in a sorted list of numbers).

How to Find the Median Value

To find the Median, place the numbers you are given in value order and find the middle number.

Example: find the Median of {12, 3 and 5} |
---|

Put them in order: |

3, 5, 12 |

The middle number is 5, so the median is 5. |

Example 2 |
---|

Look at these numbers: |

3, 13, 7, 5, 21, 23, 39, 23, 40, 23, 14, 12, 56, 23, 29 |

If we put those numbers in order we have: |

3, 5, 7, 12, 13, 14, 21, 23, 23, 23, 23, 29, 39, 40, 56 |

There are fifteen numbers. Our middle number will be the eighth number: |

3, 5, 7, 12, 13, 14, 21, 23, 23, 23, 23, 29, 39, 40, 56 |

The median value of this set of numbers is 23. |

(Note that it didn't matter if we had some numbers the same in the list)

Two Numbers in the Middle

BUT, if there are an even amount of numbers things are slightly different.

In that case we need to find the middle pair of numbers, and then find the value that would be half way between them. This is easily done by adding them together and dividing by two.

An example will help: |
---|

3, 13, 7, 5, 21, 23, 23, 40, 23, 14, 12, 56, 23, 29 |

If we put those numbers in order we have: |

3, 5, 7, 12, 13, 14, 21, 23, 23, 23, 23, 29, 40, 56 |

There are now fourteen numbers and so we don't have just one middle number, we have a pair of middle numbers: |

3, 5, 7, 12, 13, 14, 21, 23, 23, 23, 23, 29, 40, 56 |

In this example the middle numbers are 21 and 23. |

To find the value half-way between them, add them together and divide by 2: |

21 + 23 = 44 |

44 ÷ 2 = 22 |

And, so, the Median in this example is 22. |

(Note that 22 was not in the list of numbers ... but that is OK, because half the numbers in the list are less, and half the numbers are greater.)

public class Median { private Median() { } public static void swap(int[] a, int i1, int i2) { int temp = a[i1]; a[i1] = a[i2]; a[i2] = temp; } public static int find(int[] a, int from, int to) { int low = from; int high = to; int median = (low + high) / 2; do { if (high <= low) { return a[median]; } if (high == low + 1) { if (a[low] > a[high]) { swap(a, low, high); } return a[median]; } int middle = (low + high) / 2; if (a[middle] > a[high]) { swap(a, middle, high); } if (a[low] > a[high]) { swap(a, low, high); } if (a[middle] > a[low]) { swap(a, middle, low); } swap(a, middle, low + 1); int ll = low + 1; int hh = high; do { do { ll++; } while(a[low] > a[ll]); do { hh--; } while(a[hh] > a[low]); if (hh < ll) { break; } swap(a, ll, hh); } while(true); swap(a, low, hh); if (hh <= median) { low = ll; } if (hh >= median) { high = hh - 1; } } while(true); } public static void main(String arg[]) { Median a1=new Median(); int a[]={2,34,6,7,8,9,3,56,7,8} a1.find(a,0,9); } }