Python 3.2 - Find Second Smallest Number In A List Using Recursion

So I need to find the second smallest number within a list of integers using recursion but I cannot for the life of me devise a way to do it. I can do it with to find smallest numb

Solution 1:

Here is a short implementation that doesn't use min() or sorted(). It also works when there are duplicate values in the list.

defss(e):
    iflen(e)==2and e[0]<=e[1]:return e[1]
    return ss(e[:-1]) if e[0]<=e[-1]>=e[1] else ss([e[-1]]+e[:-1])

print("The selected value was:", ss([5, 4, 3, 2, 1]))

Solution 2:

This should work. get_smallest_two_items() returns a tuple with the smallest 2 elements out of the 3 inputted. Implementing it should be trivial. Also note that this assumes the minimum length of the list is 2.

defsmallest(int_list):
   smallest_two = smallest_helper(int_list)
   return smallest_two[0] if smallest_two[0]<=smallest_two[1] else smallest_two[1]

defsmallest_helper(int_list):

  if(len(int_list) == 2):
    return (int_list[0],int_list[1])
  else:
    a_b = smallest(int_list[1:])
    a = a_b[0]
    b = a_b[1]
    c = int_list[0]

    return get_smallest_two_items(a,b,c)

Solution 3:

Simpler example than my comment:

deffind_nth_smallest(n, int_list):
    smallest = min(int_list)
    if n <= 1:
        return smallest
    int_list = [v for v in int_list if v != smallest]
    if int_list:
        returnmax(find_nth_smallest(n - 1, int_list), smallest)
    returnNone

Example:

Python 2.7.8 (default, Oct 20 2014, 15:05:19) 
[GCC 4.9.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>from kthTerm import find_nth_smallest>>>import random>>>random.seed()>>>int_list = [random.randint(1, 100) for _ inrange(20)]>>>int_list
[68, 50, 6, 36, 98, 15, 81, 36, 13, 71, 76, 77, 69, 75, 79, 53, 26, 25, 18, 62]
>>>find_nth_smallest(2, int_list)
13
>>>sorted(int_list)
[6, 13, 15, 18, 25, 26, 36, 36, 50, 53, 62, 68, 69, 71, 75, 76, 77, 79, 81, 98]

Solution 4:

Here's an approach that doesn't blow the stack for large lists. It would be better to manage the search endpoints manually rather than using slicing which introduce copying.

import random

defmin2(xs):
    iflen(xs) < 3: return xs
    n = len(xs) // 2returnsorted(min2(xs[:n]) + [xs[n]] + min2(xs[n+1:]))[:2]

tk = range(100000)
random.shuffle(tk)
print min2(tk)

Solution 5:

Here is a pure recursive way. You need to return the first smallest and the second smallest element in a tuple and so on.

def smallest(int_list):

    if(len(int_list) == 2):
        if (int_list[0] >= int_list[1]):
            return (int_list[0],int_list[1])
        else:
            return (int_list[1],int_list[0])
    else:
        first_smallest,second_smallest = smallest(int_list[1:])
        current_elem = int_list[0]
        if(second_smallest <= current_elem):
            return (second_smallest,current_elem)
        else:
            if (current_elem<=first_smallest):
               return (current_elem,first_smallest)
            else:
               return (first_smallest,second_smallest)



if __name__ == "__main__":    
    small = smallest([1,2,3,4])
    print small[1]
    //output 2