Class Median

java.lang.Object
topics.divideconquer.median.Median
public class Median extends Object

Median Calculation

Finds the median of an unsorted array. This class demonstrates the evolution from a brute-force sorting approach to the highly optimized Quickselect algorithm.

Even Length Definition

Note: For arrays with an even number of elements, there are technically two medians. This algorithm follows the standard integer division convention (N/2), which targets the upper median element mathematically.

Author:
vicegd

  • Constructor Details

    • Median

      public Median()

  • Method Details

    • medianBySorting

      public int medianBySorting(int[] v)

      1. Sorting Approach

      Sorts the entire array to easily extract the central element. While conceptually simple, it does unnecessary work by fully ordering the elements on the left and right sides of the median.

      • Time Complexity: O(N log N) - Bound by the Quicksort step.
      • Space Complexity: O(N) - We clone the array to prevent mutating the user's original data.
      Parameters:
      v - Array of integers.
      Returns:
      The median value.

    • medianQuickselect

      public int medianQuickselect(int[] v)

      2. Quickselect Approach (Divide invalid input: '&' Conquer)

      Uses the Quicksort partition scheme to recursively isolate the median. If the pivot lands perfectly on the median index, we stop immediately. If it lands to the right or left, we recursively search ONLY the relevant half, discarding the other half completely.

      • Time Complexity: O(N) average case. O(N²) worst case.
      • Space Complexity: O(N) for cloning + O(log N) call stack.
      Parameters:
      v - Array of integers.
      Returns:
      The median value.