Finding the Median in an Array: A Step-by-Step Tutorial

In this tutorial, we’ll walk through the process of finding the median of an array of integers. We’ll explain the fundamental concepts involved and solve the problem using both C++ and Python.

Problem Statement

Given an array arr[] of N integers, calculate the median. The median is the middle value in an ordered list of numbers. If the list has an even number of elements, the median is the average of the two middle numbers. We need to return the floor value of the median.

Examples

Example 1:

Input: N = 5
arr[] = {90, 100, 78, 89, 67}
Output: 89
Explanation: After sorting the array, the middle element is the median.

Example 2:

Input: N = 4
arr[] = {56, 67, 30, 79}
Output: 61
Explanation: In case of an even number of elements, the average of the two middle elements is the median.

Fundamental Concepts

1. Median:
   • For an odd number of elements: The median is the middle element after sorting.
   • For an even number of elements: The median is the average of the two middle elements.
2. Sorting:
   • Sorting the array is essential to find the median. The time complexity for sorting an array is O(n log n).
3. Floor Value:
   • The floor value of a number is the greatest integer less than or equal to the number. In our case, it is essential to return the integer part of the median.

Approach

1. Sort the Array: Sorting the array will help in easily locating the middle elements.
2. Find the Middle Element(s):
   • If the number of elements N is odd, the median is the middle element.
   • If N is even, the median is the average of the two middle elements.
3. Return the Floor Value: Return the integer part of the median.

C++ Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int find_median(vector<int>& arr) {
    int n = arr.size();
    sort(arr.begin(), arr.end());
    
    if (n % 2 == 1) {
        // Odd number of elements
        return arr[n / 2];
    } else {
        // Even number of elements
        int mid1 = arr[(n / 2) - 1];
        int mid2 = arr[n / 2];
        return floor((mid1 + mid2) / 2.0);
    }
}

int main() {
    vector<int> arr1 = {90, 100, 78, 89, 67};
    vector<int> arr2 = {56, 67, 30, 79};
    
    cout << "Median of arr1: " << find_median(arr1) << endl; // Output: 89
    cout << "Median of arr2: " << find_median(arr2) << endl; // Output: 61
    
    return 0;
}

Python Solution

def find_median(arr):
    arr.sort()
    n = len(arr)
    
    if n % 2 == 1:
        # Odd number of elements
        return arr[n // 2]
    else:
        # Even number of elements
        mid1 = arr[(n // 2) - 1]
        mid2 = arr[n // 2]
        return (mid1 + mid2) // 2

# Example Usage
arr1 = [90, 100, 78, 89, 67]
arr2 = [56, 67, 30, 79]

print(f"Median of arr1: {find_median(arr1)}")  # Output: 89
print(f"Median of arr2: {find_median(arr2)}")  # Output: 61

Explanation

1. Sorting: Both solutions start by sorting the array.
2. Finding the Median:
   • For an odd-sized array, the middle element is directly taken as the median.
   • For an even-sized array, the average of the two middle elements is computed.
3. Returning the Floor Value:
   • In Python, using integer division // automatically gives the floor value.
   • In C++, using floor function ensures we get the floor value of the average.

Conclusion

Finding the median involves sorting the array and then determining the middle value(s). This problem helps in understanding basic sorting and median-finding algorithms, which are fundamental in statistics and data analysis. The provided solutions in both C++ and Python should help in grasping the concept and applying it in different programming environments.