Python Data Structures and Algorithms

Partitioning step

Now that we have obtained the approximate median, the get_index_of_nearest_median function takes the bounds of the list indicated by the first and last parameters:

    def get_index_of_nearest_median(array_list, first, second, median):         if first == second:             return first         else:             return first + array_list[first:second].index(median) 

Once again, we only return the first index if there is only one element in the list. The arraylist[first:second] returns an array with index 0 up to the size of the list -1. When we find the index of the median, we lose the portion in the list where it occurs because of the new range indexing the [first:second] code returns. Therefore, we must add whatever index is returned by arraylist[first:second] ...