Home » Data Structure » Array Data Structure

Median in a stream of integers (running integers)

C++ implementation to find the median in a stream of integers (running integers).
Submitted by Vikneshwar GK, on February 05, 2022

Consider a situation where integers are read from a data stream. The task at hand is to analyze the data and output the median of the elements. The median is the middle number in a sorted, ascending, or descending, list of numbers. If the number of elements is even, then find the average of the middle two elements.

To avoid complications, let us assume that there are no duplicates in the data stream.

Example:

If the input data stream is 
5, 1, 7, 8, 9, 3, 2, 1, 5, 6

Then the output will be like,
Median after reading 1 element is 5
Median after reading 2 elements is 3
Median after reading 3 elements is 5
Median after reading 4 elements is 6
Median after reading 5 elements is 7
Median after reading 6 elements is 6
Median after reading 7 elements is 5
Median after reading 8 elements is 4
Median after reading 9 elements is 5
Median after reading 10 elements is 5

Explanation:
When input is 5,
then median is 5

When next input is 1, after sorting,
it will be 1, 5. So median is 3

When next input is 7, after sorting,
it will be 1, 5, 7. So median is 5

And so on...

Solution:

In order to find the median, we need to sort the data stream. Since technically, we will be getting the data one by one, it will be efficient if we sort them as they appear. Insertion sort is the best algorithm to facilitate this purpose but the time complexity of this algorithm is huge-O(n²). We can also try using binary search on insertion algorithm, yet it doesn't provide efficient time complexity.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function that perform binary search
// finds the placement of current element
int binarySearch(int array[], int element, int low, int high)
{
    if (low >= high) {
        return (element > array[low]) ? (low + 1) : low;
    }

    int mid = (low + high) / 2;

    if (element == array[mid])
        return mid + 1;

    if (element > array[mid])
        return binarySearch(array, element, mid + 1, high);

    return binarySearch(array, element, low, mid - 1);
}

// Function to print median of stream of integers
void printMedian(int array[], int length)
{
    int i, j, index, element;
    int count = 1;

    cout << "Median after reading 1"
         << " element is " << array[0] << "\n";

    for (i = 1; i < length; i++) {
        float median;
        j = i - 1;
        element = array[i];

        // find the position to be inserted at
        index = binarySearch(array, element, 0, j);

        // move elements to right to create space to insert
        // the current element
        while (j >= index) {
            array[j + 1] = array[j];
            j--;
        }

        array[j + 1] = element;

        // increment count of sorted elements in array
        count++;

        // if odd, select the middle element
        if (count % 2 != 0) {
            median = array[count / 2];
        }
        // if even, find the mean of middle two elements
        else {
            median = (array[(count / 2) - 1] + array[count / 2])
                / 2;
        }

        cout << "Median after reading " << i + 1
             << " elements is " << median << "\n";
    }
}

// Main function
int main()
{
    int array[100], N, x;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    printMedian(array, N);

    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1:5
Enter element 2:1
Enter element 3:7
Enter element 4:8
Enter element 5:9
Enter element 6:3
Enter element 7:2
Enter element 8:1
Enter element 9:5
Enter element 10:6
Median after reading 1 element is 5
Median after reading 2 elements is 3
Median after reading 3 elements is 5
Median after reading 4 elements is 6
Median after reading 5 elements is 7
Median after reading 6 elements is 6
Median after reading 7 elements is 5
Median after reading 8 elements is 4
Median after reading 9 elements is 5
Median after reading 10 elements is 5

Time Complexity: O(n²), where n is the length of the data stream.