You are viewing a single comment's thread. Return to all comments →
The way I did this is to notice that we are certain of only the location of the pivot, if we have l items less than the pivot, then the pivot is in the lth position, if the we count from 0. The median is the object at the len(ar)//2 position starting at 0 for odd number arrays.
So we try to find that position.
If the position we are looking for is in the left partition we just recurse for the same position on the left side (pos < len(leftside))
If the position is in the right side we recurse on that side to search for position pos- len(leftside) -1
Since the positions in the right side start after the leftside positions + 1 for the pivot.
Eventually you will get an array of size one and a search for position 0, which only has a pivot and no right or left side, and you have found the answer.
This method should find any kth order statistic, such as the 0th or minimum and the len(ar)-1 th or maximum