finding middle element of an array [duplicate]

Question

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?

Answer 1

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]