Let's say you took a number x
.
Let L
be the set of numbers less than x
in the array, size of the set is |L|
Let E
be the set of numbers equal to x
in the array, size of the set is |E|
Let G
be the set of numbers larger than x
in the array, size of the set is |G|
Let's imagine the sorted array, the first |L|
numbers (1 -> |L|)
are contained in set L
.
The following |E|
numbers (|L|+1 -> |L|+|E|)
are contained in set E
.
The following |G|
numbers (|L|+|E|+1 -> end)
are contained in set G
.
We are looking for the kth
smallest number, so we have 3 cases:
1) k <= |L|
this means that the number we are looking for is in the first |L|
numbers in the sorted array, so we search for the kth
smallest number in L
.
2) |L| < k <= |L|+|E|
this means that the number we are looking for is in a position between (|L|+1 -> |L|+|E|)
in the sorted array, so it is an element from E
. Since all elements of E
are equal to x
, we know that the kth
smallest number is equal to x
.
3) k > |L|+|E|
this means that the number we are looking for is in a position between (|L|+|E|+1 -> end)
in the sorted array, so it is an element from 'G'. Since there are already |L|+|E|
numbers less than the kth
smallest number, we can subtract |L|+|E|
from k
, let's call it k'
(k' = k - |L| - |E|
), and search for the k'th
smallest element in G
.