(C/C++)1つの配列を与え、1つの主要素が存在するかどうかを決定する:分治法(nlogn)

1つの配列1...nの半数以上の要素が同じである場合、この配列は1つの主要素を含むと呼ばれる.配列を指定し、有効なアルゴリズムを設計し、配列にプライマリ要素が含まれているかどうかを決定し、ある場合は、この要素を見つけます.この配列の要素間には必ずしも順序が存在しないが、整数間に順序が存在する場合、A[i]>A[j]のような比較が可能であり、これとは異なり、その配列の要素は必ずしもこのような比較が可能ではない.(たとえばこの配列の要素をGIFファイルとして想像することができます)しかし、定数時間内に「A[i]==A[j]と答えることはできますか?」アルゴリズムを与えて、nlognで本題の要求を完成します(ヒント:配列Aを2つの配列A 1とA 2に分けて、それぞれAの半分の要素を含みます.以下の問題を考えます:A 1とA 2のそれぞれの主な要素を知っていたら、Aの中の主な要素を探し出すのに役立ちますか?答えが肯定的であれば、あなたは1種の分治方法を使うことができます)
構想
A 1とA 2の主元素が同じである場合、その主元素もAの主元素であるA 1とA 2が1つの主元素しか存在しない場合、Aの主元素(O(n))であるかどうかを遍歴検査する.A 1とA 2に主元素が存在しない場合、Aに主元素が1つしか存在しない場合、その元素はAの主元素である

#include 
// -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 << "
";
}

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;
}