You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.

▲ timv 2 days ago | parent | next [-]

You can use Quickselect (https://en.wikipedia.org/wiki/Quickselect) or Floyd-Rivest (https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm)

Quickselect is fairly simple to understand if you already understand Quicksort. You use use a binary division but you avoid sorting sections where the order doesn't matter.

Let's start with a 7 element array

    [ 2, 4, 7, 5, 3, 6, 1 ]

We pivot on the mid-point (5) so that values less than end before it in the array and numbers larger end up after it

    [ 2, 4, 3, 1, 5, 7, 6 ]

Since 5 is now at an index greater than the midpoint, you know the median must be less than 5, so you don't care that 7 and 6 aren't sorted.

We pivot the first partition (first 4 elements) on 3 and get

   [ 2, 1, 3, 4, 5, 7, 6 ]

We don't care that 2 and 1 are unsorted, because we know that the median is > 3 (3 is at index #2 and we want index #3), so the median must be 4

▲

AdieuToLogic 2 days ago | parent [-]

And what of the likelihood that the original collection is modified when using the quickselect algorithm, thus introducing observable side effects in what could reasonably be considered a "read-only" computation?

	▲	timv 2 days ago \| parent [-]
		And there lies the tradeoffs you need to consider as part of an interview question. But if the best alternative is to sort the whole collection, then Quickselect doesn't introduce a new problem. You either accept that modifying the collection in place is an acceptable behaviour (and describe that in your API docs) or you make a copy of the collection and operate on that. Given a choice between quickselect and quicksort, quickselect will get the answer with less overhead and no additional constraints (because it's essentially the same algorithm with unnecessary steps removed). There are alternative approaches that don't require a full copy/sort, but they either require a partial copy + partial sort, or multiple passes through the collection.

▲ strstr 2 days ago | parent | prev | next [-]

You can definitely do this without sorting.

QuickSelect is average case n, and is, roughly, quick sort where you throw away one of the sides each time and recurse on the other. This has a fat tail for cases where you pick a bad pivot (similar to quicksort), but you can median-of-medians your way out of that problem if someone cares. (Median of medians being where you subdivide the array into, say, 5 arrays, recursively compute the median on those, and pick the middle median as your pivot, which guarantees linear progress per iteration)

	▲	AdieuToLogic 2 days ago \| parent [-]
		> You can definitely do this without sorting. > QuickSelect is ... Quickselect implementations can, and often do, partially sort the underlying collection: `As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data.[0]` If you are aware of a quickselect implementation having O(n) average performance which does not modify the underlying collection, I would very much appreciate a reference to same. 0 - https://en.wikipedia.org/wiki/Quickselect

▲ scarmig 2 days ago | parent | prev [-]

You can solve it with two heaps, which don't need to maintain a complete order. Or selection algorithms, as in the sibling comment (asymptotically better).