typedef int DataType;

//此函数用于逆转数组,left是逆转开始的最左侧,right为最右侧,arraySize是数组大小,用于防止越界
bool Reverse(DataType A[], int left, int right, int arraySize)
{
    if(left >= right || right >= arraySize)
        return false;
    int mid = (left + right) / 2;
    for(int i = 0; i <= mid - left; i++)
    {
        DataType temp = A[left + i];
        A[left + i] = A[right - i];
        A[right - i] = temp;
    }
}

void Exchange(DataType A[], int m, int n, int arraySize)
{
    // 下面三步为思路中的三步
    Reverse(A, 0, m + n - 1, arraySize);
    Reverse(A, 0, n - 1, arraySize);
    Reverse(A, n, m + n - 1, arraySize);
}

bool Reverse(int R[], int from, int to)
{
    int i, temp;
    for(i = 0; i < (to - from + 1); i++)
    {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

//数组R，一共有n个元素，向左移动p个元素
//即前p个元素和后n-p个元素换位置
void Exchange(int R[], int n, int p, int arraySize)
{
    // 下面三步为思路中的三步
    Reverse(A, 0, p - 1);
    Reverse(A, p, n - 1);
    Reverse(A, 0, n - 1);
}

int M_Search(int A[], int B[], int n)
{
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    // 分别表示序列A和B的首位数，末位数和中位数（下标）
    while (s1 != d1 || s2 != d2)
    {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2])
        {
            return A[m1];               //满足条件1
        }
        if (A[m1] < B[m2])              //满足条件2
        {
            if ((s1 + d1) % 2 == 0)     //若元素个数为奇数
            {
                s1 = m1;                //舍弃A的中间点以前的部分,保留中间点
                d2 = m2;                //舍弃B的中间点以后的部分,保留中间点
            }
            else                        //元素个数为偶数
            {
                s1 = m1 + 1;            //舍弃A中间点及以前的部分
                d2 - m2;                //舍弃B的中间点以后的部分,保留中间点
            }
        }
        else                            //满足条件3
        {
            if ((s1 + d1) % 2 == 0)     //若元素个数为奇数
            {
                d1 = m1;                //舍弃A的中间点以后的部分,保留中间点
                s2 = m2;                //舍弃B的中间点以前的部分,保留中间点
            }
            else                        //元素个数为偶数
            {
                d1 = m1;                //舍弃A的中间点以后的部分,保留中间点
                s2 = m2 + 1;            //舍弃B中间点及以前的部分
            }
        }
    }
    return (A[s1] < B[s2]) ? A[s1] : B[s2];
}

int Majority(int A[], int n)
{
    int i, c, count = 1;        //c用来保存候选主元素，count用来计数
    c = A[0];                   //设置A[0]为候选主元素
    for (i = 1; i < n; i++)     //查找候选主元素
    {
        if (A[i] == c)
        {
            count++;            //对A中的候选主元素计数
        }
        else
        {
            if (count > 0)      //处理不是候选主元素的情况
            {
                count--;
            }
            else                //更换候选主元素，重新计数
            {
                c = A[i];
                count = 1;
            }
        }
    }
    if (count > 0)
    {
        for (i = count = 0; i < n; i++)//统计候选主元素的实际出现次数
        {
            if (A[i] == c)
            {
                count++;
            }
        }
    }
    if (count >= n / 2)
    {
        return c;               //确认候选主元素
    }
    else
    {
        return -1;              //不存在主元素
    }
}