You are given as input an unsorted array of n distinct numbers, where n is a power of 2. Give an algorithm that identifies the second-largest number in the array, and that uses at most n+log2n−2 comparisons.

prob_1_ADA_course.py

# https://class.coursera.org/algo-009/forum/thread?thread_id=29

def get_second_largest(nums_lst):
    """
    >>> get_second_largest([3,1,10,17,12,4])
    12
    """
    def get_greaters_lst(lst):
        if len(lst) == 1:
            return lst

        lst1 = get_greaters_lst(lst[0:int(len(lst) / 2)])
        lst2 = get_greaters_lst(lst[int(len(lst) / 2):])

        if lst1[0] > lst2[0]:
            lst1.append(lst2[0])
            return lst1
        else:
            lst2.append(lst1[0])
            return lst2

    greaters_lst = get_greaters_lst(nums_lst)[1:]
    max_num = greaters_lst[0]
    for candidate in greaters_lst:
        if candidate > max_num:
            max_num = candidate

    return max_num

if __name__ == '__main__':
    import doctest
    doctest.testmod()