c++ - Divide-and-conquer algorithm for finding the majority element?

Question

An array is said to have a majority element if more than half of its elements are the same. Is there a divide-and-conquer algorithm for determining if an array has a majority element?

I normally do the following, but it is not using divide-and-conquer. I do not want to use the Boyer-Moore algorithm.

int find(int[] arr, int size) {
    int count = 0, i, mElement;

    for (i = 0; i < size; i++) {
        if (count == 0) mElement = arr[i];

        if (arr[i] == mElement) count++;
        else count--;
    }

    count = 0;
    for (i = 0; i < size; i++) {
        if (arr[i] == mElement) count++;
    }

    if (count > size / 2) return mElement;
    return -1;
}

Answer 1

I can see at least one divide and conquer method.

Start by finding the median, such as with Hoare's Select algorithm. If one value forms a majority of the elements, the median must have that value, so we've just found the value we're looking for.

From there, find (for example) the 25th and 75th percentile items. Again, if there's a majority element, at least one of those would need to have the same value as the median.

Assuming you haven't ruled out there being a majority element yet, you can continue the search. For example, let's assume the 75th percentile was equal to the median, but the 25th percentile wasn't.

When then continue searching for the item halfway between the 25th percentile and the median, as well as the one halfway between the 75th percentile and the end.

Continue finding the median of each partition that must contain the end of the elements with the same value as the median until you've either confirmed or denied the existence of a majority element.

As an aside: I don't quite see how Boyer-Moore would be used for this task. Boyer-Moore is a way of finding a substring in a string.