(C/C++)给定一个数组，确定是否存在一个主元素：分治法(nl

当一个数组1...n超过半数的元素都相同时，该数组被称为含有一个主元素。给定一个数组，设计一个有效算法，确定该数组是否含有一个主元素，如果有，找出这个元素。该数组的元素之间不一定存在顺序，如果整数之间就存在顺序，可以作形如A[i]>A[j]的比较，与此不同的是，该数组的元素则不一定能做出这样的比较。（比如可以将该数组的元素想象成GIF文件）但是，却可以在常量时间内回答“A[i]==A[j]吗？”
给出一个算法，以nlogn完成本题的要求（提示：将数组A划分成两个数组A1和A2，各含有A的一半元素。考虑以下问题：如果知道了A1和A2的各自主元素，是否对找出A中的主元素有所帮助？如果答案是肯定的，你就可以使用一种分治方法）

思路

如果A1和A2的主元素相同，则该主元素也为A的主元素
如果A1和A2只存在一个主元素，遍历检查是否为A的主元素（O(n)）
如果A1和A2均不存在主元素，则A不存在主元素
如果A只有一个元素，则该元素为A的主元素

#include <iostream>
//设-1为不会出现的数
#define UNDEFINED (-1)
#define LENGTH 10
using namespace std;

int INDEX[10] = { 3,2,2,2,3,3,8,3,3,3 };

bool checkMainNum(int begin, int end, int num) {
    int count = 0;
    for (int i = begin; i <= end; i++) {
        if (INDEX[i] == num)
            count++;
    }
    
    if (count > (end - begin + 1) / 2) {
        cout << begin << "-->" << end << ":" << num << endl;
        return true;
    }
    return false;
}

int hasMainNum(int begin,int end) {
    if (begin == end)
        return INDEX[begin];
    int mid = (begin + end) / 2;
    int leftMain = hasMainNum(begin, mid);
    int rightMain = hasMainNum(mid + 1, end);
    //若左右主元素均存在
    if (leftMain != UNDEFINED && rightMain != UNDEFINED) {
        //若左右主元素相同
        if (leftMain == rightMain)
            return leftMain;
        //若左右主元素不同
        if (checkMainNum(begin, end, leftMain))
            return leftMain;
        if (checkMainNum(begin, end, rightMain))
            return rightMain;
        return UNDEFINED;
    }
    //仅左主元素存在
    else if (leftMain != UNDEFINED) {
        if (checkMainNum(begin, end, leftMain))
            return leftMain;
        return UNDEFINED;
    }
    else if (rightMain != UNDEFINED) {
        if (checkMainNum(begin, end, rightMain))
            return rightMain;
        return UNDEFINED;
    }
    return UNDEFINED;
}

void showIndex(int* index,int length) {
    for (int i = 0; i < length; i++)
        cout << index[i] << " ";
    cout << "\n";
}

int main(void) {
    cout << "数组为:";
    showIndex(INDEX, LENGTH);
    int mainNum = hasMainNum(0, LENGTH - 1);
    if (mainNum == UNDEFINED) {
        cout << "不存在主元素" << endl;
    }
    else {
        cout << "主元素为:" << mainNum << endl;
    }
    system("pause");
    return 0;
}