Numbers arrive one at a time. You do not get to see the full list up front — they stream in, one after another, endlessly. At any moment, someone taps you on the shoulder and asks: what is the median right now?

Not the mean. Not the max. The median — the value that sits exactly in the middle when everything is lined up in order. If you have seen seven numbers, the median is the 4th smallest. If you have seen a hundred, it is the 50th and 51st, averaged.

This is not a textbook exercise. Streaming medians power real systems: monitoring server response times where you need to ignore outliers, tracking the middle score in a live leaderboard, computing percentiles for data that never stops arriving. The constraint is always the same — you cannot wait for all the data, because all the data never comes.

Your first instinct is probably: keep the numbers sorted. And that instinct is smart. A sorted array makes finding the median trivial — just index into the middle. For an array of length n, the median lives at arr[Math.floor(n / 2)]. Constant time. Done.

And when a new number arrives? Binary search finds the correct insertion position in O(log n) comparisons. You know exactly where the new element belongs before you even touch the array.

But there is a cost hiding inside that instinct. Binary search tells you where the element goes. It does not make room for it. The array is a contiguous block of memory — every element to the right of the insertion point has to slide over by one position to open up a gap. That is not O(log n). That is O(n).

A sorted array of five numbers is waiting below. A queue of new numbers needs to be inserted, one at a time, in sorted order. Tap each number to drop it in, and watch what the array has to do to make room.

The counter kept climbing. Each insertion forced more elements to shuffle right than the one before. Three insertions in, and already the cost is accelerating.

Two more numbers are still waiting in the queue. What do you think happens next?

You predicted acceleration. Now watch the proof unfold — the last two insertions play out automatically, and the curve tells the full story.

Every insertion forced the array to shift elements to the right — one by one, starting from the end, working back to the insertion point. The first insertion might shift just one or two elements. But by the fifth insertion, the array is longer, and a badly-placed number can push almost everything aside.

This is not linear growth. Each insertion is more expensive than the last, because each insertion operates on a longer array. The first costs at most 5 shifts. The second costs at most 6. The third, 7. For n insertions into a growing array, the total number of shifts is proportional to 1 + 2 + 3 + ... + n — which is O(n^2).

Binary search was never the bottleneck. It did its job in O(log n) every time. The bottleneck was the physical act of making room — shoving elements aside so the new one could take its place. You optimized the search. The shift was always the real cost.

Take a step back and look at what you maintained: a perfectly sorted array. Every element knows its exact rank relative to every other element. Element at index 0 is the smallest. Element at index n-1 is the largest. The ordering is total and complete.

But the only question anyone ever asked was: what sits in the middle?

You did not need to know that arr[0] < arr[1]. You did not need to know that arr[n-2] < arr[n-1]. You needed to know exactly one thing — which value is at the median position. All that shifting, all that O(n) work per insertion, was the price of maintaining an ordering that was far more precise than the question demanded.

Try it yourself — tap to add numbers and watch the median marker. Notice how the other dots are irrelevant to it. The median only cares about its own position in the middle.

There is a principle buried here. If full sorted order costs O(n) per insertion but you only need the middle element, then maybe you do not need full sorted order. Maybe there is a way to maintain just enough structure to answer the median question — without the expense of keeping everything in its exact place. A kind of partial order where the two halves of the data know their boundaries, but the elements within each half are free to sit however they like.

You felt the shifting — elements sliding right, one by one, to make room. Now write the code that does exactly that. Two blanks, two pieces of the inner loop.

You just proved that maintaining perfect sorted order costs O(n) per insertion — and for streaming data, that adds up to O(n^2) total. The sorting was never wrong. It was just too precise for the question being asked.

The next screen introduces a structure that maintains partial order — enough to answer the median question in O(1), with insertions that cost only O(log n). Instead of one sorted array, you will split the data into two halves that each know their boundary but not their internal order. That is the two-heaps pattern.