Selecting the "P" in Prune and Search Algorithm

StackOverflow https://stackoverflow.com/questions/17665113

  •  03-06-2022
  •  | 
  •  

Question

enter image description here

Note: the diagram above shows a partition into groups of 5 (the columns). The horizontal box denotes the median values of each partition. The 'P' item indicates the median of medians.

Most of the researches that I saw have this picture in Selecting their "P" and it always have an odd numbers of elements. But What if the numbers elements you have are even?

ex.

 1  2  3  4  5  6  7  8  9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60

how do you get your "P" in an even set of elements?

Was it helpful?

Solution

This explanation gives the detail I think you're looking for:

https://www.cs.duke.edu/courses/summer10/cps130/files/Edelsbrunner_Median.pdf

The median of the set plays a special role in this algorithm, and it is defined as the i-smallest item where i = (n+1)/2 if n is odd and i = n/2 or (n+2)/2 if n is even.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top