Understanding Randomized Select algorithm
The function Randomized-Partition accepts an array $A[p],\ldots,A[r]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A[p],\ldots,A[q-1] \leq A[q] \leq A[q+1],\ldots,A[r]$.

The location of the pivot $q$ within the array is $k := q-p+1$. That is, $q$ is the $k$th smallest element in $A[p],\ldots,A[r]$. To see this, let us assume from now on that all elements of $A$ are distinct (this will slightly simplify the arguments). Then the $q-p$ elements $A[p],\ldots,A[q-1]$ are smaller than $A[q]$, and the rest are larger than $A[q]$.

If $i = k$, then we are done. If $i &lt; k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[p],\ldots,A[q-1]$ (since the $i$th smallest element is smaller than $A[q]$, which is the $k$th smallest element), and moreover, it is the $i$th smallest element in that subarray. If $i &gt; k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[q+1],\ldots,A[r]$ (since the $i$th smallest element is larger than $A[q]$, which is the $k$th smallest element), and moreover, it is that $(i-k)$th smallest element in that subarray (since the $k$ elements $A[p],\ldots,A[q]$ are already smaller than it).