finding middle element of an array

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?

Are there any other constraints, the number of elements will be odd? — Mariy, Jan 09 '11 at 14:40
Is this always a sequence of *n* consecutive numbers from 1 to *n*? — Gumbo, Jan 09 '11 at 14:41
Should be in C language. Yes, number of elements will be odd. No, its not a sequence. Can be in any order like 100,9,35,7,23 and the output will be 23 — senthil, Jan 09 '11 at 15:30

Saeed Amiri · Answer 1 · 2011-01-09T14:56:12.183

2

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]

edited Jan 09 '11 at 14:56

answered Jan 09 '11 at 14:43

Saeed Amiri

22,252
5
45
83

No, its not consecutive. Can be of any order. Like 34,19,45,12,2 and the Answer should be 19 – senthil Jan 09 '11 at 15:35
@senthil, in this way my first answer is what you want, read and search about it to understand it. – Saeed Amiri Jan 09 '11 at 15:41

score 0 · Answer 2 · answered Jan 09 '11 at 14:39

0

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

answered Jan 09 '11 at 14:39

Johan Kotlinski

25,185
9
78
101

score 0 · Answer 3 · answered Jan 09 '11 at 15:29

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.

finding middle element of an array

3 Answers3