Median

The median is the middle value separating the higher half from the lower half of a dataset. It is less sensitive to outliers than the mean.

To find the median:

Sort the dataset
If odd number of values, median is middle value
If even number of values, median is average of two middle values

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
double median(int[] nums) {
  Arrays.sort(nums);

  int n = nums.length;
  if (n % 2 == 0) {
    return (nums[n/2] + nums[n/2 - 1]) / 2.0; 
  } else {
    return nums[n/2];
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
double median(vector<int> nums) {
  sort(nums.begin(), nums.end());

  int n = nums.size();
  if (n % 2 == 0) {
    return (nums[n/2] + nums[n/2 - 1]) / 2.0;
  } else {
    return nums[n/2];
  }
} 

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from statistics import median

def data_median(nums):
  return median(nums)

# Or manually
def manual_median(nums):
  nums.sort()
  n = len(nums)
  mid = n // 2
  if n % 2 == 0:
    return (nums[mid] + nums[mid-1]) / 2
  else:
    return nums[mid]

The median divides a dataset into high and low values and gives robust measure of central tendency.

Here are the implementations for calculating the median of an array of integers.

Description:

Given an array of integers, the task is to find the median. The median is the middle number in a sorted sequence. If the sequence has an odd length, the median is the middle number; if the sequence has an even length, the median is the average of the two middle numbers.

Java:

In Java, we need to sort the array and then find the middle element(s).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;

public class MedianCalculator {
    public static double median(int[] numbers) {
        Arrays.sort(numbers);
        int n = numbers.length;
        if (n % 2 != 0) {
            return (double) numbers[n / 2];
        } else {
            return (double) (numbers[(n - 1) / 2] + numbers[n / 2]) / 2;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {40, 10, 30, 20};
        System.out.println("Median: " + median(numbers)); // Output: Median: 25.0
    }
}

C++:

In C++, we can use the sort function from the <algorithm> library and then find the middle element(s).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>

double median(std::vector<int>& numbers) {
    std::sort(numbers.begin(), numbers.end());
    int n = numbers.size();
    if (n % 2 != 0) {
        return static_cast<double>(numbers[n / 2]);
    } else {
        return static_cast<double>(numbers[(n - 1) / 2] + numbers[n / 2]) / 2;
    }
}

int main() {
    std::vector<int> numbers = {40, 10, 30, 20};
    std::cout << "Median: " << median(numbers) << std::endl; // Output: Median: 25
    return 0;
}

Python:

In Python, we can use the sort method on the list and then find the middle element(s).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def median(numbers):
    numbers.sort()
    n = len(numbers)
    if n % 2 != 0:
        return numbers[n // 2]
    else:
        return (numbers[(n - 1) // 2] + numbers[n // 2]) / 2

numbers = [40, 10, 30, 20]
print("Median:", median(numbers)) # Output: Median: 25.0

These examples cover finding the median for an array of integers in Java, C++, and Python. They sort the numbers and then return the middle element or the average of the two middle elements, depending on whether the length of the numbers is odd or even.

In the Median of Two Sorted Arrays problem, we return the median of the two sorted arrays. The solution must have run time complexity O(log (m + n)).