7

I am trying to calculate the median of a sorted array of numbers in C++ and I was wondering if there is a built in function in the C++ library that does this.

  • 3
    *"sorted array with an unknown size"* What does that mean? You need *some* way to tell where the arrays ends, and you thus know the size. – Baum mit Augen Feb 03 '17 at 22:04
  • There's no median function in the C++ standard library. Related question: [Compute Median of Values Stored In Vector - C++?](http://stackoverflow.com/q/2114797/3425536) – Emil Laine Feb 03 '17 at 22:12

2 Answers2

13

There's no need to use a function. To find the median of a list with an odd number of items, just do

cout << sortedArray[size/2];

where sortedArray is the array and size is the size of the array. For an array with an even number, you should just do something like this

cout << (sortedArray[size/2] + sortedArray[(size/2) - 1])/2

In other words, take the average of the n/2 element and the n/2-1 element.

If you don't know the size, you need to loop through the array and count how many elements there are. Doing it with decimals is irrelevant because the size of an array is always a whole number.

Gab
  • 1,007
  • 9
  • 22
  • 5
    What if there's an even number of elements? You'd want to take the average of the two in the middle. e.g. median of 2 4 6 8 should be 5. – Greg Kikola Feb 03 '17 at 22:03
  • 3
    For the second case, I think you want `size/2 - 1` and `size/2` as the indices. – Greg Kikola Feb 03 '17 at 22:09
  • Ok, although what should I use to declare size? I am getting an error that says size wan't declared in this scope. –  Feb 03 '17 at 22:13
  • size should be the size of the array. If you don't readily have it, you need to iterate through the array until the end and count how many elements there are. – Gab Feb 03 '17 at 22:14
  • @GabrieleB-David: He can get the size using the operator `sizeof` instead of iterating. – Raindrop7 Feb 03 '17 at 22:19
  • @Raindrop7 That's true, but in the end the compiler just iterates over the array to find its size so there is no significant speed improvement and when learning this stuff, it's better to know how to do these things explicitly. – Gab Feb 03 '17 at 22:27
  • @GabrieleB-David: Can a compiler iterate over elements of array without knowing its size? If so please show me? – Raindrop7 Feb 03 '17 at 22:29
  • @GabrieleB-David *"in the end the compiler just iterates over the array to find its size"* Huh? Where did you get that idea? – Baum mit Augen Feb 03 '17 at 22:32
  • @Raindrop7 I misunderstood your comment. I thought you meant the size of function in the c standard library. Apologies – Gab Feb 03 '17 at 23:55
  • 1
    The principle of this answer is great - but do be aware of the possibility of [integer overflow when computing the semi-sum](https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html) when the values are very large. Have a look at [Salvatore Ruggieri's paper](http://pages.di.unipi.it/ruggieri/Papers/semisum.pdf) for some robust algorithms. – Toby Speight Jan 17 '18 at 09:23
0

If you know the size of the sorted array, you can compute its median in O(1). When the size is unknown (is it a linked list or what?), then counting the median would take O(n) on a classical computer.

bipll
  • 11,747
  • 1
  • 18
  • 32