# Upper Median Selection

# 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:

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

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$.

```id="um1"
upper_median(A):
    n = length(A)
    k = n // 2
    return quickselect(A, k)
```

## Example

Let:

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

Sorted order:

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

The upper median index is:

$$
k = \lfloor 4 / 2 \rfloor = 2
$$

So the result is:

$$
7
$$

## 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

| 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 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

```id="um2"
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
```

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