Central Tendency

Median Search

Find the median — the middle value of an ordered dataset. First sort the values by repeatedly picking the smallest remaining element (min-pick), then select the centre position. With an odd number of values the median is the exact middle element; with an even count it is the mean of the two middle values. By hand, min-pick makes the ordering visible step by step.

By hand

Copy the values into remaining, then loop: each iteration picks m = min(remaining), appends it to sv, and removes it from remaining. The trace shows remaining shrinking and sv growing in sorted order — 4, 6, 6, 8, 9, 10, 13 — one element at a time. After the loop, sv[n // 2] picks the element at index 3, the centre of a seven-element array.

naive.py
Replay: real traced execution (multi-file project)
values = [4, 8, 6, 13, 10, 6, 9]
remaining = list(values)
sv = []
while remaining:
    m = min(remaining)
    sv.append(m)
    remaining.remove(m)
n = len(sv)
median = sv[n // 2]
print('RESULT:', median)

  1. values ← [4, 8, 6, 13, 10, 6, 9]

    1values = [4, 8, 6, 13, 10, 6, 9]2remaining = list(values)
    values this step[4, 8, 6, 13, 10, 6, 9]values

  2. remaining ← [4, 8, 6, 13, 10, 6, 9]

    1values = [4, 8, 6, 13, 10, 6, 9]2remaining = list(values)3sv = []
    values this step[4, 8, 6, 13, 10, 6, 9]remaining

  3. sv ← []

    2remaining = list(values)3sv = []4while remaining:
    values this step[]sv

  4. m ← 4, sv ← [4], remaining ← [8, 6, 13, 10, 6, 9]

    pass 1 of 7
    3sv = []4while remaining:5    m = min(remaining)6    sv.append(m)7    remaining.remove(m)8n = len(sv)
    values this step4m[] → [4]sv[4, 8, 6, 13, 10, 6, 9] → [8, 6, 13, 10, 6, 9]remaining
    All 7 passes — pass 1 is the card above
    passmsvremaining
    14[] → [4][4, 8, 6, 13, 10, 6, 9] → [8, 6, 13, 10, 6, 9]
    24 → 6[4] → [4, 6][8, 6, 13, 10, 6, 9] → [8, 13, 10, 6, 9]
    3—[4, 6] → [4, 6, 6][8, 13, 10, 6, 9] → [8, 13, 10, 9]
    46 → 8[4, 6, 6] → [4, 6, 6, 8][8, 13, 10, 9] → [13, 10, 9]
    58 → 9[4, 6, 6, 8] → [4, 6, 6, 8, 9][13, 10, 9] → [13, 10]
    69 → 10[4, 6, 6, 8, 9] → [4, 6, 6, 8, 9, 10][13, 10] → [13]
    710 → 13[4, 6, 6, 8, 9, 10] → [4, 6, 6, 8, 9, 10, 13][13] → []

  5. while remaining:

    3sv = []4while remaining:5    m = min(remaining)

  6. n ← 7

    7    remaining.remove(m)8n = len(sv)9median = sv[n // 2]
    values this step7n

  7. median ← 8

    8n = len(sv)9median = sv[n // 2]10print('RESULT:', median)
    values this step8median

  8. stdout ← RESULT: 8

    9median = sv[n // 2]10print('RESULT:', median)
    values this stepRESULT: 8stdout

With the library

statistics.median handles both odd and even counts. np.median returns the same value as a float.

library.py 
import statistics
import numpy as np
from dalib.display import set_display
set_display()

values = [4, 8, 6, 13, 10, 6, 9]
median_stdlib = statistics.median(values)
median_numpy = float(np.median(values))
print('statistics.median:', median_stdlib)
print('np.median:        ', median_numpy)
print('RESULT:', median_stdlib)

statistics.median: 8
np.median:         8.0
RESULT: 8

Implementation notes

  • For even n, statistics.median averages the two middle values (returns a float if they differ). The naive sv[n // 2] picks the upper-middle element — add explicit even-n handling if exact parity with the library is required.
  • The median is robust to outliers: replacing 13 with 1000 leaves the result unchanged at 8. The mean would shift significantly.
  • Cross-reference: arithmetic-mean (this chapter) to see how the mean reacts to the same outlier.