Lower Median Selection

Lower Median Selection returns the lower median of a sequence. For even length arrays, there are two central elements. The lower median is the smaller of the two.

This definition is common in discrete settings where a single representative element must be chosen.

Problem

Given an array $A$ of length $n$, return the element with rank:

$$ k = \left\lfloor \frac{n - 1}{2} \right\rfloor $$

That is:

• for odd $n$, the unique median
• for even $n$, the lower of the two middle elements

Algorithm

Use a selection method such as Quickselect or Nth Element.

lower_median(A):
    n = length(A)
    k = (n - 1) // 2
    return quickselect(A, k)

Example

Let:

$$ A = [7, 2, 9, 4] $$

Sorted order:

$$ [2, 4, 7, 9] $$

The lower median index is:

$$ k = \lfloor (4 - 1) / 2 \rfloor = 1 $$

So the result is:

$$ 4 $$

Correctness

The lower median is defined as the element with rank $\lfloor (n - 1)/2 \rfloor$. Selection algorithms correctly return the element with any specified rank, so applying selection with this index yields the lower median.

Complexity

method	time
Quickselect average	$O(n)$
deterministic select	$O(n)$
sort	$O(n \log n)$

Space:

$$ O(1) $$

for in-place selection.

When to Use

Use Lower Median when:

• you need a stable single representative for even-sized data
• tie-breaking must favor smaller values
• deterministic behavior is required in discrete systems

This variant is common in statistics, scheduling, and load balancing.

Implementation

def lower_median(a):
    def quickselect(a, k):
        import random

        left, right = 0, len(a) - 1

        def partition(l, r, p):
            pivot = a[p]
            a[p], a[r] = a[r], a[p]
            store = l
            for i in range(l, r):
                if a[i] < pivot:
                    a[store], a[i] = a[i], a[store]
                    store += 1
            a[r], a[store] = a[store], a[r]
            return store

        while True:
            if left == right:
                return a[left]

            p = random.randint(left, right)
            p = partition(left, right, p)

            if k == p:
                return a[k]
            elif k < p:
                right = p - 1
            else:
                left = p + 1

    k = (len(a) - 1) // 2
    return quickselect(a, k)

func LowerMedian(a []int) int {
	k := (len(a) - 1) / 2
	return Quickselect(a, k)
}