Re^2: Puzzle: The Ham Cheese Sandwich cut.

It depends how you look at the problem. If you look at it as the 1-d variant of the "divide sets using a simplex" problem, any number between the two middle numbers will do. However, if you want to write a Quick Sort whose running time is garanteed to be O(N log N), you need to find a median in linear time, and you want to find an element of the set - not something in between.

Wether you find one of the middle elements, or pick a number in between, I'll accept both solutions. ;-).

Perl --((8:>*

Comment on Re^2: Puzzle: The Ham Cheese Sandwich cut.

Replies are listed 'Best First'.
Re^3: Puzzle: The Ham Cheese Sandwich cut. by ambrus (Abbot) on Nov 19, 2005 at 18:10 UTC
Are you sure in this? Once you have found a number so that exactly half of the numbers are to the left and half are to the right, couldn't you separate these two classes of numbers, sort them separately, and still get an O(N log N) time sort this way? If I have to define median, I'd say that if you have an even number of data, any number between the two middle one is a median. This way the definition is equivalent then if you say that the median is a number whose total distance from the given numbers is minimal. This latter definition has paraleles: the mean is the number for which the square sum of its distance from the given numbers is minimal. More clearly, given the sequence (x_1, ..., x_N), the mean is the number A that minimizes the expression \|x_1 - A\|^2 + ... + \|x_N - A\|^2; the median is M if it minimizes \|x_1 - M\| + ... + \|x_N - M\|. Furthermore, informally speaking, the modus C minimizes \|x_1 - C\|^epsilon + ... + \|x_N - C\|^epsilon, where epsilon is a very small positive number.	[reply]
Re^4: Puzzle: The Ham Cheese Sandwich cut. by Perl Mouse (Chaplain) on Nov 20, 2005 at 16:21 UTC
Are you sure in this? Once you have found a number so that exactly half of the numbers are to the left and half are to the right, couldn't you separate these two classes of numbers, sort them separately, and still get an O(N log N) time sort this way? Well, yes, that is the point. However, to archieve this, you 1) must divide the set into pieces in linear time and 2) each subset must contain at least cN numbers, for some `0 < c < 1`. Using the median as the pivot to divide the set satisfies condition 2), but to satisfy condition 1), you need to find the median in linear time. `Perl --((8:>*`	[reply]