# Lower Median Selection

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

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

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

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