Divide and Conquer Algorithm

[tlang07uky]

I've been stuck on a divide a conquer algorithm problem for about an hour now, and I'm not sure how to solve it. I need to use divide-and-conquer to implement an algorithm that finds the dominant element of an array of positive integers and returns -1 if the array does not have a dominant element (a dominant element is one that occurs in more than half the elements of a given array).

No sorting may be used, and the only comparison that may be used is a test for equality.

I understand the general process I need to follow to solve this problem, but I'm not sure exactly how to convert my thoughts to code. I know that if a number x is the dominant element of an array A, the x must be the dominant element in either the first half of A, the second half of A, or both.

Here is what I have so far.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int find_dominant(int *A, int p, int r)
{
return 0;
}

int main(int argc, char * argv[])
{

int myArray [14] = {3, 3, 3, 1, 2, 3, 3, 5, 4, 3, 3, 3, 2, 1};
int n;
n = sizeof myArray/sizeof(int);
find_dominant(myArray, 0, n-1);
return 0;
}

The program must run in O(n log n) time.
I know that this isn't much to go off, but I am relatively new to C++.
Any and all help would be appreciated!

[tfityo]

You can look at http://stackoverflow.com/questions/4280450/linear-time-majority-algorithm
But this is not a divide&conquer algorithm

As a d&c I may recommend to find a median (linear time, http://en.wikipedia.org/wiki/Selection_algorithm) and then check if this element is a dominant one. But median search will require comparison.

[tlang07uky]

Thanks for the input tfityo, I didn't find either link helpful. I just need to find out how many times each number occurs in the array, and if any number occurs in more than half the elements, output that number to the console.

I was never taught how to do some of the stuff required for this program, so any help is still appreciated!