finding middle element of an array [duplicate]

This question already has answers here: 开发者_StackOverflow中文版 Closed 12 years ago.

Possible Duplicate:

How to find the kth largest element in an unsorted array of length n in O(n)?

Hi all, I came cross a question in my interview.

Question:

Array of integers will be given as the input and you should find out the middle element when sorted , but without sorting.

For Example.

Input: 1,3,5,4,2

Output: 3

When you sort the given input array, it will be 1,2,3,4,5 where middle element is 3.

You should find this in one pass without sorting.

Any solutions for this?

---

This is a selection algorithm problem which is O(n).

Edit: but if you sure items are consecutive you can compute smallest and biggest and count of elements (in one pass) and return [smallest + (biggest - smallest + 1)/ 2]

---

To me, it sounds like you can use std::nth_element straight off - don't know if that is an acceptable answer.

---

You can use a "modified" quicksort to find it. It runs in O(n^2) but should be fairly fast on average. What you do is every time you choose a pivot, you check how many elements were less than the pivot and how many were greater. If there are same elements less and greater than the pivot, the pivot is the median. If not, you can recurse only to the portion where the element is contained. Worst case scenario, you will be performing a complete sorting though.

Example:

Array with 7 elements, we are looking for the 4-th smallest element.

5 3 8 6 7 1 9

Suppose quicksort chooses 3 as pivot, than you'll get:

1 3 5 8 6 7 9

Now, you want the 2nd smallest in the subarray [5, 8, 6, 7, 9]. Keep going until the pivot is the k-th smallest you are searching in the current iteration.

I think this solution is pretty good for an interview question although you should mention that there is an O(n) deterministic solution.