Find the 1st and 2nd largest num in an array, O(log N) + O(N) version

I have implemented the \$O(logN) + O(N)\$ version for the problem: How to find 1st and 2nd largest element in a non-negative unique array? The algorithm principle is from this stackoverflow answer.The comparison information in finding 1st helps find 2nd faster (\$log N\$ time).

But I am really depressed that my code is even slower than the easiest method. Theoretically, lower the numbers of comparison, smaller the cost time. I guess maybe my implementation need be optimized.

Can anyone know how to make algorithm2 faster than the easiest method?

Tested the code in VS2013, win 10, CPU i5 6500, release version.

The result: algo1 30ms, algo2 96ms.

My code, mian.cpp:

```
// You need focus on algo2 function.
#include
#include
#include
#include
#include

#include
#include

#include "gettime.h"
using namespace std;

vector algo1(vector src_data);
vector algo2(vector src_data);
vector generateRandNum(unsigned int size);

int main() {
vector src_data;
vector result;
src_data = generateRandNum(10000000);

uint64 t0 = GetTimeMs64();
result = algo1(src_data);
uint64 t1 = GetTimeMs64();
cout generateRandNum(unsigned int size) {
int num = 0;
vector src_data;

for (size_t i = 0; i algo1(vector src_data) {
int max1st = -1, max2rd = -1;
int record = 0;
vector result;
// find maximum num
for (size_t i = 0; i max1st) {
max1st = src_data[i];
record = i;
}
}
for (size_t i = 0; i max2rd) {
max2rd = src_data[i];
}
}
result.push_back(max1st);
result.push_back(max2rd);
return result;
}

vector algo2(vector src_data) {
vector> matrix;
// initial first row
matrix.push_back(src_data);

// build the tree using 2D vector
int layer_size = src_data.size();
int height = 0;
int maximum = 0;
int lastnode = 0;
int newsize = 0;
int num1, num2;
int aplus = 0, isnegtive = 0;
while (layer_size != 1) {

Algo 1 still has a lot of headroom for improvement as well:

vector algo1(const vector &src_data) {
    int max1st = src_data[0], max2nd = src_data[1];
    if (max1st  max2nd) {
            if (n > max1st) {
                max2nd = max1st;
                max1st = n;
            } else {
                max2nd = n;
            }
        }
    });

    vector result;
    result.push_back(max1st);
    result.push_back(max2nd);
    return result;
}

For starters, avoid copying src_data on invocation. That is easily 50% of the function cost with the original solution, and 70% for the OP's improved solution.

The second improvement, only ever perform the n > max1st comparison if n > max2nd has confirmed it as a potential candidate. Best case, the number of comparisons drops to \$n\$ with \$\mathcal{O}(1)\$ assignments, and only the worst case remains \$2n\$ comparisons with \$2n\$ assignments.

A quick benchmark of the original, the improved, and this implementation of algo1 (when using the copy free function signature, best out of 3 each), took 19ms, 12ms and 8ms each.

StackExchange Code Review Q#141635, answer score: 4