## Finding The Median

### September 11, 2015

The median of an array is the value in the middle if the array was sorted; if the array has an odd number of items *n*, the median is the (*n*+1)/2’th largest item in the array (which is also the (*n*+1)/2’th smallest item in the array), and if the array has an even number of items *n*, the median is the arithmetic average of the *n*/2’th smallest item in the array and the *n*/2’th largest item in the array. For instance, the median of the array [2,4,5,7,3,6,1] is 4 and the median of the array [5,2,1,6,3,4] is 3.5.

Your task is to write a program that takes an array of 8-bit integers (possibly but not necessarily in sort) and finds the median value in the array; you should find an algorithm that takes linear time and constant space. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Similar solution in Perl:

Clever! My knee-jerk reaction was to ignore the 8-bit integer part and just go for the slower generic solution.

I’ve used this as an opportunity to learn some Rust. I like that it made me think about the empty array case.

Python solution.

@graham, I think you have an “off by one error”. In the loop ‘lo’ is incremented before use, so the value of count[0] is never added to lo_count. Similarly, ‘hi’ is pre-decremented, so count[255] is never added to hi_count.

@Mike: good eye! Sorry for the errors, all.

[…] Programming Praxis problem. The problem is nicely constrained by limiting it to 8-bit […]

It looks like my solution (along with the issue @Mike caught) doesn’t correctly handle the case of a single element array. Apologies!

#!/usr/bin/perl -w

use strict;

my @array = qw/1 2 3 4 9 10 11/;

print median(@array);

sub median

{

my @vals = sort {$a $b} @_;

my $len = @vals;

if($len%2) #odd?

{

return $vals[int($len/2)];

}

else #even

{

return ($vals[int($len/2)-1] + $vals[int($len/2)])/2;

}

}

#include

int main()

{

int a[10],i,j,n;

printf(“Enter the no of events\n”);

scanf(“%d”,&n);

printf(“Input\n”);

for(i=0;i<n;i++)

scanf("%d",a+i);

for(i=1;i<n;i++)

for(j=0;j

a[i])a[j] = a[j]*a[i]/(a[i]=a[j]);

printf(“Output\n”);

for(i=0;i %d”,a[n/2]);

else

printf(“Median is -> %d”,(a[n/2]+a[n/2 -1])/2);

}