Difference between Quickselect & Binary Search Selection

Question

I've had some good breakthroughs understanding some of the more advanced algorithms for sorting, selecting, searching etc.

Here's the scenario I'm stuck on however.

With an array of values, in which you want to find the kth smallest element, you can use use quickselect if it's unsorted, and a binary search if it is sorted.

If I understand correctly, via a pivot/partition system, quickselect will search an unsorted data set by choosing a pivot, creating groups of lows and highs by comparing each element to the pivot, and then recursively breaking down the lists into sublists via a changing pivot.

This sounds very similiar to how a binary search works, so why is it that quickselect works on unsorted values and binary search doesn't, and doesn't all the comparing in a quickselect algorithm (to work out the lows and highs) take a lot of ... cost?

Answer 1

Binary search does NOT determine the k-th smallest element: it's NOT a selection algorithm. Binary search determines if a value you supply as input is in the array or not.

A selection algorithm determines the k-th smallest element. If the array is already sorted, as in the case of binary search, then selecting the k-th smallest element can be done in O(1), simply using k as an index into the array.

To recap: with quickselect you can determine for instance the 8-th smallest element in the array, while with binary search you can search if an element with value 15 is in the array or not.

Quickselect can select an arbitrary order statistics in expected O(n) time; binary search can search for an element in O(log n) time but requires the array to be sorted, otherwise the algorithm will not be correct. As I told you, selecting the k-th smallest element in a sorted array is trivial, requiring O(1) time to access the k-th element in the sorted array.

Finally, searching for an element (a given value) when the array is not sorted requires in the worst case O(n) time since you need to perform a linear scan of the array.