Weighted Median

The concept of a weighted median extends the traditional median by incorporating weights for each element. In a sorted list, the weighted median is the element ( x ) such that at least half of the total weight is less than ( x ) and at least half is greater than or equal to ( x ).

Table Illustrating Weighted Median

Let’s assume we have an array arr = [1, 2, 3, 4] and corresponding weights weights = [2, 3, 1, 4].

Here’s how the table will look like:

Element	Weight	Cumulative Weight
1	2	2
2	3	5
3	1	6
4	4	10

First, we find the total weight, which is (2 + 3 + 1 + 4 = 10).
Then, we find half of the total weight, ( \frac{10}{2} = 5 ).

Starting from the first element and going through the array:

The cumulative weight after 1 is (2), which is less than (5).
The cumulative weight after 2 is (5), which is equal to (5).

So, the weighted median is 2, as at least half of the total weight is less than or equal to 2, and at least half is greater than or equal to 2.

Key Points

Cumulative weight helps in finding where the weighted median lies.
Once the cumulative weight reaches or exceeds half of the total weight, we find our weighted median.

Solution

Java

Here’s how you can calculate the weighted median in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class WeightedMedian {
    public static double findWeightedMedian(int[] arr, int[] weights) {
        int n = arr.length;
        double totalWeight = 0;
        for (int w : weights) {
            totalWeight += w;
        }
        double halfWeight = totalWeight / 2.0;
        double currentWeight = 0;

        for (int i = 0; i < n; ++i) {
            currentWeight += weights[i];
            if (currentWeight >= halfWeight) {
                return arr[i];
            }
        }
        return -1;  // Shouldn't happen for well-formed input
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int[] weights = {3, 1, 4};
        System.out.println(findWeightedMedian(arr, weights));
    }
}

C++

Here’s how to do it in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>

double findWeightedMedian(std::vector<int>& arr, std::vector<int>& weights) {
    int n = arr.size();
    double totalWeight = 0;
    for (int w : weights) {
        totalWeight += w;
    }
    double halfWeight = totalWeight / 2.0;
    double currentWeight = 0;

    for (int i = 0; i < n; ++i) {
        currentWeight += weights[i];
        if (currentWeight >= halfWeight) {
            return arr[i];
        }
    }
    return -1;  // Shouldn't happen for well-formed input
}

int main() {
    std::vector<int> arr = {1, 2, 3};
    std::vector<int> weights = {3, 1, 4};
    std::cout << findWeightedMedian(arr, weights) << std::endl;
}

Python

And finally, in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def find_weighted_median(arr, weights):
    total_weight = sum(weights)
    half_weight = total_weight / 2.0
    current_weight = 0

    for i in range(len(arr)):
        current_weight += weights[i]
        if current_weight >= half_weight:
            return arr[i]
    return -1  # Shouldn't happen for well-formed input

arr = [1, 2, 3]
weights = [3, 1, 4]
print(find_weighted_median(arr, weights))

Key Takeaways

The weighted median takes into account the weights of elements, not just their values.
The weighted median can be found by iterating through the sorted array and summing the weights until they reach or exceed half of the total weight.
The Java, C++, and Python examples show a straightforward way to calculate the weighted median.

Describe the Concept of Weighted Median

The weighted median is an extension of the median concept to datasets where each data point has an associated weight. In a sorted dataset, the weighted median is the element ( x ) for which at least half of the total weight is on each of its sides. This measure is particularly useful in datasets where certain observations carry more significance than others.

Java Code for Weighted Median

In Java, you can find the weighted median as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class WeightedMedian {
    public static double findWeightedMedian(int[] arr, double[] weights) {
        double totalWeight = 0;
        for (double weight : weights) {
            totalWeight += weight;
        }

        double halfWeight = totalWeight / 2.0;
        double currentWeight = 0;
        
        for (int i = 0; i < arr.length; i++) {
            currentWeight += weights[i];
            if (currentWeight >= halfWeight) {
                return arr[i];
            }
        }
        return -1;  // Invalid case
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 6, 8};
        double[] weights = {0.1, 0.2, 0.3, 0.25, 0.15};
        double result = findWeightedMedian(arr, weights);
        System.out.println("The weighted median is: " + result);
    }
}

Calculate the total weight using a loop.
Loop through the array, accumulating the weight until you cross half of the total weight.

C++ Code for Weighted Median

In C++, the weighted median can be computed similarly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

double findWeightedMedian(int arr[], double weights[], int size) {
    double totalWeight = 0;
    for (int i = 0; i < size; ++i) {
        totalWeight += weights[i];
    }

    double halfWeight = totalWeight / 2.0;
    double currentWeight = 0;

    for (int i = 0; i < size; ++i) {
        currentWeight += weights[i];
        if (currentWeight >= halfWeight) {
            return arr[i];
        }
    }
    return -1;  // Invalid case
}

int main() {
    int arr[] = {1, 3, 4, 6, 8};
    double weights[] = {0.1, 0.2, 0.3, 0.25, 0.15};
    double result = findWeightedMedian(arr, weights, 5);
    std::cout << "The weighted median is: " << result << std::endl;
}

The steps are quite similar to Java, with array and weight size passed as arguments to the function.

Python Code for Weighted Median

In Python, the code is straightforward:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def find_weighted_median(arr, weights):
    total_weight = sum(weights)
    half_weight = total_weight / 2.0
    current_weight = 0
    
    for i in range(len(arr)):
        current_weight += weights[i]
        if current_weight >= half_weight:
            return arr[i]

if __name__ == "__main__":
    arr = [1, 3, 4, 6, 8]
    weights = [0.1, 0.2, 0.3, 0.25, 0.15]
    result = find_weighted_median(arr, weights)
    print(f"The weighted median is: {result}")

Use Python’s sum function to sum up the weights.
Loop through the list, adding up the weights, and find the point where the sum crosses the half-weight mark.

In all three languages, the code calculates the total weight first and then iteratively sums the weights until it finds the element where the sum is at least half the total weight. This element is the weighted median.