Median search

From Wikipedia, the free encyclopedia

A median search is an algorithm that finds the median value of list. It belongs to the "divide and conquer" algorithm category and more precisely it is a selection algorithm. A selection algorithm finds the kth element of a list with N elements. To calculate the median, we set k = (N + 1)/2 at the selection algorithm.

1 Algorithm
2 See also
3 References
4 External links

[edit] Algorithm

The median search algorithm results in finding the median in a unsorted array of numbers. Algorithm could be as follows:- input parameters:- An array => a[];

                   median value => median= n/2     if n is even.
                                         = (n-1)/2 if n is odd.

output parameter:- result => median of the array.

// let f(a) be a funtion that returns the size of the array a[].

int mediansearch(median,a[])
{
    int x=a[median];
 // create three array.. a1[],a2[],a3[].
 // a1[] has elements lesser than x.
 // a2[] has elements equal to x.
 // a3[] has elements greater than x.
 
    if( f(a1) >= median )
       return mediansearch(median,a1[]);
    if( ( f(a1)+f(a2) ) >= median )
       return x;  
    else
       return mediansearch( median - (f(a1)+f(a2)),a3);
}