Finding Second Largest Element in an Array

Question

Here's my implementation using divide and conquer in C++.

What do you think of this implementation regarding running time ?

#include <iostream>
#include <tuple>
using namespace std;

tuple <int,int> largest_two_numbers(int *arr,int size)
{
    //The algorithm is based on returning a tuple with the largest two numbers in the array

    if (size==1)
        return tuple<int,int>(arr[0],arr[0]);
    if (size==2)
        return tuple<int,int>(arr[0],arr[1]);

    //Split the arr into two arrays
    int arr_1[size/2],arr_2[size/2+(size&1)];
    for (int i = 0; i < size/2; ++i)
    {
        arr_1[i]=arr[i];
        arr_2[i]=arr[i+size/2];
    }
    if (size&1) arr_2[size/2]=arr[size-1];

    //Return two tuples one for the right half and the other for the left
    tuple <int,int> right= largest_two_numbers(arr_1,size/2);
    tuple <int,int> left = largest_two_numbers(arr_2,size/2+(size&1));

    //Declare an array maxis with the values inside the two tuples combined and find the largest two numbers
    int maxis[]={get<0>(right),get<1>(right),get<0>(left),get<1>(left)};
    int max1=maxis[0],max2=maxis[0];
    for (int i = 0; i < 4; ++i)
    {
        if (maxis[i]>max1) max1=maxis[i];
    }
    for (int i = 0; i < 4; ++i)
    {
        if (maxis[i]>max2 && maxis[i]<max1) max2=maxis[i];
    }

    //Return a tuple with the largest two numbers
    return tuple<int,int>(max1,max2);
}

int main(){
    int arr[]={-1,98,22,1,0,301,112},n=7;

    //Print the second largest element in the array which is the second element in the tupple
    cout << get<1>(largest_two_numbers(arr,n));
}

Answer 1

Inefficient algorithm

As stated in the comments, the algorithm is actually pretty convoluted. One cannot find the maximum without looking at all of the elements, if they don't have any idea about the pattern of the input.

On top of that, it allocates quite a lot of memory.

Non-standard C++

VLA (variable length array) is not part of C++. It might be an extension in your compiler

Using C++ as C

The code is extremely imperative. It has a lot of control that it doesn't use, and doesn't have any benefit over standard algorithms. It is also bound to int arrays, to pointers, in fact. May be as C code it would be ok (if algorithm problems are fixed), but this is not effective usage of C++ features.

Benchmarking

Usually when seriously talking about performance people also use benchmarks. Having some real statistics on multiple platforms will strengthen your argument.

Alternative approach

Now that we know that we need to pass through anyway, lets write simple loop over the whole range:

#include <functional>
#include <array>
#include <utility>

template <typename ForwardIterator, typename Compare = std::less<>>
std::array<ForwardIterator, 2> find_2greatest(ForwardIterator first, 
                                              ForwardIterator last,
                                              Compare cmp = {})
{
    if (first == last)
    {
        return {first, first};    
    }

    auto greatest = first;
    auto runner_up = greatest;

    for (++first; first != last; ++first)
    {
        if (cmp(*runner_up, *first))
        {
            runner_up = first;   
            if (cmp(*greatest, *runner_up))
            {
                std::swap(greatest, runner_up);   
            }
        }
    }

    return {greatest, runner_up};
}

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v{1, 1, 2, 3, 4, 5, 6};

    auto greatest2 = find_2greatest(std::begin(v), std::end(v));

    std::cout << "the greatest: " << *greatest2.front() << '\n'
              << "second greatest: " << *greatest2.back() << '\n';
}

The code doesn't return the objects themselves. They might be non-copyable, or user might want only the location of those elements. In general, C++ search algorithms usually return iterators. Also it is not bound to only vectors or ints, it can work on anything that allows multiple passed over the range. Your naming might be better than mine though.