Offensive Security Researcher & Quantum Cryptography Analyst

Medians and Order Statistics: Finding Minimum and Maximum Efficiently

Abdul Wahab Junaid

When I study the problem of finding the smallest or largest element in a set of data, I am really studying a special case of a broader topic called order statistics. An order statistic simply means the value that would occupy a given position if I sorted the data — the minimum is the 1st order statistic, the maximum is the nth order statistic, and the median sits somewhere in the middle. In this file, I focus specifically on the minimum and maximum, because they are the simplest and most frequently used order statistics in practice. I care about this topic because almost every data-driven task I encounter — from validating sensor ranges to building priority queues to running database queries — eventually needs to know “what is the smallest value here?” or “what is the largest value here?” Understanding how to answer that efficiently is foundational before I move on to harder order-statistic problems like finding the median or the k-th smallest element.

History and Background

I trace the formal treatment of order statistics back to statistics and probability theory, where mathematicians studied the distribution of the smallest and largest values in a random sample long before computer science existed as a discipline. In the mid-20th century, as sorting and searching became central problems in computer science, researchers began asking a sharper question: instead of sorting an entire array just to find its extremes, could I find them with fewer comparisons? This question was formalized in the algorithms community and is discussed extensively in Introduction to Algorithms by Cormen, Leiron, Rivest, and Stein (CLRS), which I treat as the canonical reference for this topic. The specific technique of finding the minimum and maximum together using paired comparisons — reducing the total comparison count below the naive 2n approach — is often credited to early analyses of comparison-based algorithms from the 1970s, and it remains a standard example used to teach the concept of a comparison lower bound.

Problem Statement

I define the problem as follows: given an unsorted array of n elements, I want to determine the smallest element (minimum), the largest element (maximum), or both, using as few comparisons as possible. I am not allowed to assume the data has any special structure — I must work with arbitrary, unsorted values. The naive approach of sorting the array first and then reading off the first and last elements works, but it costs me $O(n \log n)$ time. My goal is to solve this problem in linear time, and ideally with the minimum possible number of comparisons, since comparisons are typically the dominant cost in comparison-based algorithms.

Core Concepts

I rely on a few core ideas throughout this discussion:

How It Works

Finding the minimum alone (or maximum alone):

  1. I initialize a candidate variable to the first element of the array.
  2. I scan through the remaining n − 1 elements one at a time.
  3. For each element, I compare it to my current candidate.
  4. If the new element is smaller (for minimum) or larger (for maximum), I update my candidate.
  5. After scanning the entire array, my candidate holds the correct minimum (or maximum).

Finding the minimum and maximum together (efficient paired approach):

  1. I process the elements in pairs rather than one at a time.
  2. For each pair, I first compare the two elements against each other.
  3. I then compare the smaller of the pair against my current minimum candidate, and the larger of the pair against my current maximum candidate.
  4. This way, each pair costs me only 3 comparisons instead of 4 (2 comparisons per element × 2 elements).
  5. If n is odd, I handle the leftover single element by comparing it directly against both the running minimum and maximum.

Working Principle

The internal logic behind the naive single-pass approach is straightforward: since I have no prior knowledge about where the minimum or maximum might be, I must inspect every single element at least once — I cannot skip any element and still guarantee correctness. This is why n − 1 comparisons is unavoidable for finding just the minimum (or just the maximum).

The internal logic behind the paired approach is more subtle. By comparing elements against each other first, I eliminate one element from being a maximum-candidate before comparing it to the running maximum, and I eliminate the other from being a minimum-candidate before comparing it to the running minimum. This “elimination before comparison” trick is what reduces my total comparison count from 2n to roughly 3n/2, without sacrificing correctness.

Mathematical Foundation

I express the lower bound for finding the minimum alone as:

$$ T_{min}(n) = n – 1 $$

This is because I must compare every element at least once to rule it out as the minimum, and a tournament argument shows that n − 1 comparisons are both necessary and sufficient.

For finding the minimum and maximum simultaneously, I derive the tight bound using the pairing strategy:

$$ T_{min,max}(n) = \left\lceil \frac{3n}{2} \right\rceil – 2 $$

I can justify this formula by considering that I process elements in $\lfloor n/2 \rfloor$ pairs, each costing 3 comparisons, plus a small correction for odd n and for initialization. This bound is proven optimal using an adversary argument: I imagine each element starts as “unclassified,” and I track how many comparisons are required to move every element into one of four states — “possibly minimum,” “possibly maximum,” “eliminated from both,” or “possibly both.” A careful counting argument shows no comparison-based algorithm can do better than this bound.

Diagrams

flowchart TD
    A[Start: unsorted array of n elements] --> B{n is odd?}
    B -- Yes --> C[Set min = max = first element; process remaining n-1 elements in pairs]
    B -- No --> D[Take first two elements; smaller becomes initial min, larger becomes initial max]
    C --> E[For each pair: compare pair elements to each other]
    D --> E
    E --> F[Compare smaller of pair with current min]
    F --> G[Compare larger of pair with current max]
    G --> H{More pairs remaining?}
    H -- Yes --> E
    H -- No --> I[Return min and max]

Pseudocode

ALGORITHM FindMinMax(A, n)
    // A is an array of n elements, indexed 1..n
    if n is odd:
        min = max = A[1]
        i = 2
    else:
        if A[1] < A[2]:
            min = A[1]
            max = A[2]
        else:
            min = A[2]
            max = A[1]
        i = 3

    while i <= n - 1:
        if A[i] < A[i+1]:
            smaller = A[i]
            larger = A[i+1]
        else:
            smaller = A[i+1]
            larger = A[i]

        if smaller < min:
            min = smaller
        if larger > max:
            max = larger

        i = i + 2

    return (min, max)

Step-by-Step Example

I walk through the array A = [12, 4, 9, 7, 15, 3], which has n = 6 (even), so I start by comparing the first two elements.

  1. Compare A[1]=12 and A[2]=4 → min = 4, max = 12.
  2. Next pair: A[3]=9, A[4]=7 → smaller = 7, larger = 9.
    • Compare 7 with min(4): 7 is not smaller, min stays 4.
    • Compare 9 with max(12): 9 is not larger, max stays 12.
  3. Next pair: A[5]=15, A[6]=3 → smaller = 3, larger = 15.
    • Compare 3 with min(4): 3 is smaller, min becomes 3.
    • Compare 15 with max(12): 15 is larger, max becomes 15.
  4. All elements processed. Final result: min = 3, max = 15.

I used 1 (initial pair) + 2 pairs × 3 comparisons = 1 + 6 = 7 comparisons total, matching my formula: ⌈3×6/2⌉ − 2 = 9 − 2 = 7.

Time Complexity

I note that the asymptotic complexity stays linear in every case; what changes is the constant factor, which matters a great deal when n is large and comparisons are expensive (e.g., comparing complex objects or strings).

Space Complexity

I only need a fixed number of auxiliary variables — one for the running minimum, one for the running maximum, and a couple of temporary variables during pair comparisons. This gives me $O(1)$ auxiliary space, regardless of n, since I never allocate additional arrays or recursive call stacks for the iterative version.

Correctness Analysis

I argue correctness by induction on the number of elements processed. My invariant is: after processing the first k elements (or k/2 pairs), min holds the smallest value among those k elements, and max holds the largest.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

/* Finds both the minimum and maximum of an array using the paired comparison method */
void findMinMax(int arr[], int n, int *min, int *max) {
    int i;

    if (n <= 0) {
        return; /* nothing to process */
    }

    if (n % 2 != 0) {
        /* Odd length: initialize with the first element */
        *min = *max = arr[0];
        i = 1;
    } else {
        /* Even length: initialize using the first pair */
        if (arr[0] < arr[1]) {
            *min = arr[0];
            *max = arr[1];
        } else {
            *min = arr[1];
            *max = arr[0];
        }
        i = 2;
    }

    /* Process the remaining elements two at a time */
    while (i < n - 1) {
        int smaller, larger;

        if (arr[i] < arr[i + 1]) {
            smaller = arr[i];
            larger = arr[i + 1];
        } else {
            smaller = arr[i + 1];
            larger = arr[i];
        }

        if (smaller < *min) {
            *min = smaller;
        }
        if (larger > *max) {
            *max = larger;
        }

        i += 2;
    }
}

int main(void) {
    int arr[] = {12, 4, 9, 7, 15, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int minVal, maxVal;

    findMinMax(arr, n, &minVal, &maxVal);

    printf("Minimum = %d\n", minVal);
    printf("Maximum = %d\n", maxVal);

    return 0;
}

Sample Input and Output

Input:

Array: [12, 4, 9, 7, 15, 3]

Output:

Minimum = 3
Maximum = 15

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version