Divide and conquer algorithm for finding majority element of array [duplicate]

I'm trying to solve the problem for finding majority element of given array. I made two attempts to solve the problem, but seems that both have something wrong in them. First one relies on the logic that : 1) If $A$ is array with $n$ elements then $A$ has majority element $\Leftrightarrow A_{1} = A[1,...,\frac{n}{2}], A_{2} = A[\frac{n}{2} + 1, ...,n]$ both $A_{1}$ and $A_{2}$ have a majority element and the majority element of the first is equal of the majority element of the second subarray. The bottom of the recursive definition is when $A.size = 1$ then every singleton has a majority element - the only element itself.

Here is an implementation in C++ :

#include <vector>
#include <iostream>
#include <limits.h>
#define INF INT_MAX

int majority(std::vector<int>& arr, int begin, int end)
{
    if(begin == end)
        return arr[begin];
    int mid = (begin + end) / 2;
    int majorityLeft = majority(arr, begin, mid);
    int majorityRight = majority(arr, mid + 1, end);
    if(majorityLeft == majorityRight)
        return majorityLeft;
    else if(majorityLeft != majorityRight && 
            majorityLeft != INF &&
            majorityRight != INF)
        return INF;
    else if(majorityLeft != INF || majorityRight != INF)
        return std::min(majorityLeft, majorityRight);
    else return INF;
}

The second attempt relies on the Dirichlet principle. If i randomly divide the arry into $\frac{n}{2}$ pairs then at least one pair is going to satisfy the condition $\exists i,j : i \neq j, i < j \le n : A[i] = A[j]$ Then for every pair if the elements are equal i keep just one of them in new array, and if they are not equal i discard both of them. Then recussively do the same on the new array.

Here is C++ implementation :

int majority2(std::vector<int>& arr)
{
    if(arr.size() == 1)
        return arr[0];
    if(arr.size() == 0)
        return INF;
    std::vector<int> subArr;
    for(int i = 1 ; i < arr.size() ; i += 2){
        if(arr[i - 1] == arr[i])
            subArr.push_back(arr[i - 1]);
    }
    if(arr.size() % 2 == 1)
        subArr.push_back(arr[arr.size() - 1]);
    return majority2(subArr);
}

I'll be really grateful if somebody tells me what is my mistake in the implementation or algorithms' logic!