Algorithm to find the number(count > 1/2) in a array.

find_xxx.cc

#include <iostream>
#include <array>
#include <type_traits>
#include <stdexcept>
#include <algorithm>

/*! \brief get the number(count > 1/2) in array
    \note complexity time-O(N) space-O(1)
*/
template <typename ITEM, std::size_t N>
ITEM max(const std::array<ITEM, N>& a) {
        if (3 > a.size()) {
                throw std::invalid_argument("Too shorter array.");
        }
        int flag = 1;
        int target = a[0];
        for (std::size_t i = 0; i < a.size() - 1; i++) {
                if (a[i] != a[i+1]) {
                        flag--;
                } else {
                        flag++;
                        if (0 > flag) {
                                target = a[i];
                                flag = 1;
                        }
                }
        }

        // check
        std::size_t count = std::count(a.begin(), a.end(), target);
        if (count*2 <= a.size()) {
                throw std::invalid_argument("Not suitable input array.");
        }
        return target;
}

/*! \brief get the number(count > 1/2) in array
    \note complexity time-O(N) space-O(1)
*/
template <typename ITEM, std::size_t N>
ITEM max2(const std::array<ITEM, N>& a) {
        if (3 > a.size()) {
                throw std::invalid_argument("Too shorter array.");
        }
        int flag = 0;
        int target;
        for (std::size_t i = 0; i < a.size(); i++) {
                if (flag == 0) {
                        target = a[i];
                }
                if (a[i] != target) {
                        flag--;
                } else {
                        flag++;
                }
        }

        // check
        std::size_t count = std::count(a.begin(), a.end(), target);
        if (count*2 <= a.size()) {
                throw std::invalid_argument("Not suitable input array.");
        }
        return target;
}