Re: problem on medians

Finding the median is generally a lot easier as with a number of these
type of operations when all the data is stored in some particular
order to which you know. (i.e. Ascending) Then only one operation is
required to find the centre of you data set and there you have your
median.

On May 31, 9:39 am, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
ak said:

what are the least no. of comparisons to find the medain of a set of
n integers ?

I presume you mean "median".

The answer is of course 0, which occurs when n is 0, 1, or 2. For n = 0,
there is nothing to compare, so no comparisons can occur. When n is 1,
there is only one value, which is its own median, so no comparison is
required. When n is 2, the median is given by the sum of the two
elements divided by 2, and again no comparison is required.

It is also possible, albeit a little harder, to find the median in zero
comparisons when n > 2 provided only that the values are all members of
some simple arithmetic series, in any order but without any gaps and
with the highest and lowest members known.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999http://www.cpax.org.uk
email: rjh at the above domain, - www.


.

Relevant Pages

  • Re: problem on medians
    ... I presume you mean "median". ... the median is given by the sum of the two ... with the highest and lowest members known. ... Richard Heathfield ...
    (comp.programming)
  • Re: median of 3 values.
    ... Your test checks for zero arguments. ... If a median is defined to be a number, ... nil is not an acceptable value to return. ... while ash of a nonnegative integer is trivially always another ...
    (comp.lang.lisp)
  • Re: "Fair (hah) and Balanced (giggle)"
    ... the median number of times a city cop fired his or gun in earnest, ... Meaning that half the cops fired their guns less than zero times? ... officer to fire his gun, for example, 0.34 times. ... Every officer who got shot without returning fire counted as -1 ...
    (rec.arts.sf.fandom)
  • Re: Salaries for Lisp engineers
    ... The median salary for, say, experienced chess players ... is not necessarily zero just because most of them make their living ... I should think the results of such a poll would be subject to ...
    (comp.lang.lisp)
  • Re: Calculate Average in a Query
    ... >of the zero values (is it really zeros you want to ... You will have to do the Median with VBA, ... >short VBA stub. ... >Please respond to the Newsgroup, ...
    (microsoft.public.access.queries)