Попытка реализовать функцию поиска с использованием рекурсии в python

Question

Я пытаюсь уточнить k-е наименьшее значение в x, выбранном с помощью случайного разделителя, используя recusion, я уже сделал это без рекурсии, но я явно пытаюсь найти его с помощью рекурсии. Я столкнулся с x = x[1,len(x)] ValueError: ValueError: empty range for randrange() (0,0, 0)

    splitter = random.randrange(0,len(x))
    ants = x[splitter]
    lilz = []
    bigz = []
    for pigs in x:
        if pigs >= ants:
            bigz.append(pigs)
        elif pigs == ants:
            splitter
        else:
            lilz.append(pigs)
    if k == splitter:
        s = x[splitter]
    elif k < splitter:
        s =  selectR(lilz,k)
    else:
        s = selectR(bigz, k - ( len(lilz) + 1))
    return s

Answer 1

Вместо того, чтобы перебирать значения в x и разбивать его на два списка, просто отсортируйте x в первый раз, когда он передан нам, и тогда ваши оценки станут проще. Вы МОЖЕТЕ сортировать его каждый раз, но если мы добавим 3-й параметр по умолчанию False, мы можем указать при рекурсивных вызовах, что он уже отсортирован, и сэкономить некоторую работу:

import random

def selR(x, k, is_sorted=False):
    """Returns: The kth smallest value in x selected using a random splitter,
    using RECURSION.

    Parameter x: list of values
    Precondition: x contains ints or floats and len(x) > 0

    Parameter k: the rank of the value we want to find
    Precondition: k is an int in [1..n] where n is the length of x."""


    if not is_sorted:
        x = sorted(x)

    if len(x) == 1 or k <= 1:
        """
            1) Does x only have one item? Then it doesn't 
               really matter what k is, we're done.
            2) Is k <= 1? If so, then we don't need to split anymore - 
               the head of the sorted list is the desired value.
        """
        return x[0]

    """3) Find a splitter in the defined range - [1..n] where n is the length of x"""
    splitter = random.randrange(1,len(x))

    if splitter == k:
        """
            4) Is splitter the same as k? If so, we've found our value; 
              just return the tail of split list. return x[k-1]
        """
        return x[k-1]
    elif splitter > k:
        """
            5) Is splitter larger than k? If so, the kth smallest value is found
               before the split, so we recurse with selR(x[1:splitter], k-1) - we
               can start at x[1] and reduce k by one, because if x[0] was the
               kth smallest value, we would have already returned it in step 2.
        """
        return selR(x[1:splitter], k-1, True)
    else:
        """
            6) Is splitter smaller than k? Then the kth smallest value is found
               after the split return selR(x[splitter:], k-len(x[0:splitter])) -
               that is, remove items before splitter from x and reduce k by the number
               of items we just removed.
        """
        return selR(x[splitter:], k-len(x[0:splitter]), True)

# Test case
x = [1,2,1,3,4,5]
for k in range(1,len(x)+1):
    ord = { 1: "st", 2: "nd", 3: "rd" }.get(k if (k < 20) else (k % 10), 'th')
    print(f"{k}{ord} smallest element of {x}:", selR(x, k))