Median

From Algowiki
Jump to: navigation, search

Input

An ordered sequence [math]S[/math] of length [math]n[/math] such that a comparison [math]c[/math] is defined on the component type [math]C[/math] of [math]S[/math].

Output

  1. If [math]n[/math] is odd, the median is the unique value [math]x \in \{ S[1],...,S[n]\}[/math] such that
    1. [math]S[i]\lt x[/math] for at most [math]\lfloor n/2 \rfloor[/math] positions [math]i[/math] of [math]S[/math] and
    2. [math]S[i]\gt x[/math] for at most [math]\lfloor n/2 \rfloor[/math] positions [math]i[/math] of [math]S[/math].
  2. On the other hand, if [math]n[/math] is even, the median is [math](x+y)/2[/math], where [math]x,y \in \{ S[1],...,S[n]\}[/math] (let [math]x \le y[/math]) are the unique values such that
    1. [math]S[i]\lt x[/math] for at most [math]\lfloor n/2 \rfloor[/math] positions [math]i[/math] of [math]S[/math], and
    2. [math]S[i]\gt y[/math] for at most [math]\lfloor n/2 \rfloor[/math] positions [math]i[/math] of [math]S[/math].

Objective

N/A