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 "k"th element of a list with "N" elements. To calculate the median, we set "k" = ("N" + 1)/2 at the selection algorithm.
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);}
See also
* Median * Geometric median
References
External links
* Erik Demaine [http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L16/lecture16.pdf "Divide-and-conquer algorithms"]
Median — This article is about the statistical concept. For other uses, see Median (disambiguation). In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability… … Wikipedia
Median wasp — male D. media Scientific classification Kingdom: Animalia … Wikipedia
Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… … Wikipedia
Median-gland nevada springsnail — Taxobox name = Median gland nevada springsnail status = DD | status system = IUCN2.3 regnum = Animalia phylum = Mollusca classis = Gastropoda ordo = Sorbeoconcha familia = Hydrobiidae genus = Pyrgulopsis species = P. pisteri binomial =… … Wikipedia
Kd-tree — In computer science, a k d tree (short for k dimensional tree ) is a space partitioning data structure for organizing points in a k dimensional space. k d trees are a useful data structure for several applications, such as searches involving a… … Wikipedia
San Diego — This article is about the city in California. For the metropolitan area, see San Diego metropolitan area. For other meanings of San Diego , see San Diego (disambiguation). San Diego City City of San Diego … Wikipedia
Coral Springs, Florida — Coral Springs redirects here. For the neighborhood in Calgary, Alberta, see Coral Springs, Calgary. City of Coral Springs City … Wikipedia
Salinas, California — Infobox Settlement official name = City of Salinas, California settlement type = City nickname = America s Salad Bowl |250px|Old Main street in recently revived downtown Salinas. At left is Maya Cinemas, home of the largest cinema screen in… … Wikipedia
B-tree — In computer science, a B tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. It is most commonly used in databases and filesystems. In B trees, internal (non leaf)… … Wikipedia
2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… … Wikipedia
