So we can get away with recursing just once, and then this particular example,
we're going to recurse on the right side of the array.
And instead of looking for the fifth order statistic like we would originally,
we're going to recursively search for the second order statistic.
So why is that?
Well first why do we recurse on the right side of the array?
So by assumption we have this array of ten elements, we choose the pivot,
we do partitioning, remember the pivot winds up in its rightful position.
That's what partitioning does.
So in the bid it winds up in the third position,
we know it's the third smallest element in the array.
Now that's not what we were looking for.
We were looking for the fifth smallest element in the array.
That, of course, is bigger than the third smallest element of the array.
So by partitioning, where is the fifth element going to be?
It's gotta be to the right of this third smallest element,
to the right of the pivot.
So we know for sure that the fifth order statistic of the original array
lies to the right of the pivot.
That is guaranteed.
So we know where to recurse on the right hand side.
Now, what are we looking for?
We are no longer looking for the fifth order statistic,
the fifth smallest element.
Why?
Well we've thrown out both the pivot and everything smaller than it.
Remember we're only recursing on the right hand side.
So we've thrown out the pivot, the hird element, and everything less than it,
the minimum and the second minimum.
Having deleted the three smallest elements and originally looking for
the fifth smallest of what remains, of what we're recursing on.
We're looking for the second smallest element.
So the selection algorithm in general, is just the generalization of this idea.
So arbitrary arrays and arbitrary situations of whether the pivot comes back
equal to less or bigger than the element you are looking for.
So let me be more precise, I am going to call this algorithm R select for
randomized selection, and according to the problem definition it takes as input,
as usual an array A of some length n.
Then also the order statistic that we are looking for, so we are going to call
that i, and of course we assume that i is some integer between one and inclusive.
So for the base case, that is going to be if the array has size one,
then the only element we could be looking for is the oneth order statistic and
we just return the sole element of the array.