Upper Median Selection

Upper Median Selection returns the upper median of a sequence. For even length arrays, it chooses the larger of the two middle elements.

This complements the lower median and is useful when tie-breaking must favor larger values.

Problem

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

That is:

• for odd $n$, the unique median
• for even $n$, the larger of the two central elements

Algorithm

Use any selection algorithm with index $k$.

upper_median(A):
    n = length(A)
    k = n // 2
    return quickselect(A, k)

Example

Let:

Sorted order:

The upper median index is:

So the result is:

Correctness

The upper median is defined by rank $\lfloor n/2 \rfloor$. A correct selection algorithm returns the element with this rank, so the result matches the definition.

Complexity

Space:

for in-place selection.

When to Use

Use Upper Median when:

• tie-breaking must prefer larger values
• a consistent deterministic choice is required
• symmetric behavior with lower median is needed

This is useful in ranking, scheduling, and median-based partitioning schemes.

Implementation

def upper_median(a):
    import random

    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

    k = len(a) // 2
    left, right = 0, len(a) - 1

    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

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