Weighted Lower Median

The weighted lower median of a dataset is the smallest element such that the total weight of values less than it is at least half the total weight.

To find it:

Sort elements by value
Prefix sum the weights
Return smallest element where prefix sum ≥ half total weight

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int weightedLowerMedian(int[] values, int[] weights) {

  int total = 0;
  for (int w : weights) {
    total += w;
  }

  int half = total / 2;
  int prefix = 0;

  for (int i = 0; i < values.length; i++) {
    prefix += weights[i];
    if (prefix >= half) {
      return values[i];
    }
  }

  return -1; // No lower median
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int weightedLowerMedian(vector<int> values, vector<int> weights) {

  int total = accumulate(weights.begin(), weights.end(), 0);
  int half = total / 2;
  
  int prefix = 0;
  for (int i = 0; i < values.size(); i++) {
    prefix += weights[i];
    if (prefix >= half) {
      return values[i]; 
    }
  }

  return -1; // No lower median
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def weighted_lower_median(values, weights):
  
  total = sum(weights)
  half = total // 2
  
  prefix_sum = 0
  for i, value in enumerate(values):
    prefix_sum += weights[i]
    if prefix_sum >= half:
      return value
  
  return None # No lower median  

The weighted lower median is a quantile measure that incorporates weights.

A weighted (lower) median is similar to a weighted median but with a small difference. In a sorted dataset, the weighted (lower) median is the smallest element ( x ) for which at least half of the total weight is on both sides of ( x ). The term “lower” specifies that we choose the smallest such element when there are multiple possibilities.

Java Code for Weighted (Lower) Median

In Java, finding the weighted (lower) median can be done 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 WeightedLowerMedian {
    public static double findWeightedLowerMedian(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 = findWeightedLowerMedian(arr, weights);
        System.out.println("The weighted lower median is: " + result);
    }
}

C++ Code for Weighted (Lower) Median

In C++, the approach is very similar to 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
26
#include <iostream>

double findWeightedLowerMedian(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 = findWeightedLowerMedian(arr, weights, 5);
    std::cout << "The weighted lower median is: " << result << std::endl;
}

Python Code for Weighted (Lower) Median

Python offers a straightforward way to compute the weighted (lower) median:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def find_weighted_lower_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_lower_median(arr, weights)
    print(f"The weighted lower median is: {result}")

In each of these implementations, the algorithm loops through the sorted array and its corresponding weights. The sum of the weights is accumulated until it reaches at least half the total weight, and then the smallest corresponding element is returned. This element is the weighted (lower) median.