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

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 let the algorithm2 faster than the easiest method? Thank you for your patient.

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 <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

#include <stdlib.h>
#include <time.h>

#include "gettime.h"
using namespace std;

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

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

    uint64 t0 = GetTimeMs64();
    result = algo1(src_data);
    uint64 t1 = GetTimeMs64();
    cout << "Algo1 cost " << (t1 - t0) << "ms" << endl;
    cout << "1st: " << result.at(0) << " 2rd: " << result.at(1) << endl;

    t0 = GetTimeMs64();
    result = algo2(src_data);
    t1 = GetTimeMs64();
    cout << "Algo2 cost " << (t1 - t0) << "ms" << endl;
    cout << "1st: " << result.at(0) << " 2rd: " << result.at(1) << endl;

    return 0;
}

// generate unique random numbers in the range[0...N]
vector<int> generateRandNum(unsigned int size) {
    int num = 0;
    vector<int> src_data;

    for (size_t i = 0; i <= size; i++) {
        src_data.push_back(i);
    }
    std::random_shuffle(src_data.begin(), src_data.end());
    
    return src_data;
}

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

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

    // build the tree using 
    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) {
        newsize = layer_size / 2 + layer_size % 2;
        vector<int> new_row(newsize, 0);
        for (int i = 0; i < layer_size / 2; i++) {
            num1 = matrix[height][2 * i];
            num2 = matrix[height][2 * i + 1];
            maximum = max(num1, num2);
            new_row[i] = maximum;
        }
        if (layer_size % 2) {
            lastnode = matrix[height].back();
            new_row[newsize - 1] = lastnode;
        }
        matrix.push_back(new_row);
        layer_size = newsize;
        height++;
    }

    int max1st = matrix.back().front();

    // find 2nd laygest number
    int index_record = 0;
    int max2rd = -1;
    int candidate = 0;
    int leftnode_index = 0, rightnode_index = 0;
    for (int i = matrix.size() - 1; i > 0; i--) {
        leftnode_index = index_record * 2;
        rightnode_index = index_record * 2 + 1;
        if (matrix[i - 1][leftnode_index] == max1st) {
            candidate = matrix[i - 1][rightnode_index];
            index_record = leftnode_index;
        }
        else {
            candidate = matrix[i - 1][leftnode_index];
            index_record = rightnode_index;
        }
        if (candidate != max1st && candidate > max2rd) {
            max2rd = candidate;
        }
    }

    vector<int> result;
    result.push_back(max1st);
    result.push_back(max2rd);
    return result;
}

gettime.h is from http://stackoverflow.com/a/1861337/4928269.