验证候选多数元素：我的简化实现是否适用于所有场景？

问题描述 #

给定一个包含N个元素的已排序数组arr，数组中的多数元素指出现次数超过N/2次的元素。任务是编写isMajority()函数，接收数组arr[]、数组大小n和待查找数x，若x为多数元素则返回true。

标准解法 #

该解法会根据数组长度的奇偶性计算循环的lastIndex，代码如下：

static boolean isMajority(int arr[], int n, int x)
{
    int i, last_index = 0;

    /* 根据数组长度n的奇偶性计算last_index */
    last_index = (n%2==0)? n/2: n/2+1;

    /* 在arr中查找x的首次出现位置 */
    for (i = 0; i < last_index; i++)
    {
        /* 检查x是否存在且出现次数超过n/2次 */
        if (arr[i] == x && arr[i+n/2] == x)
            return true;
    }
    return false;
}

自实现简化解法 #

尝试了另一种实现方式，在部分测试用例中有效，但不确定是否适用于所有场景，代码如下：

public static boolean isMajority(int[]array,int x){
    int lastIndex=array.length-(array.length/2+1);
    for(int i=0;i<=lastIndex;i++){
        if(array[i]==x && array[i]==array[i+array.length/2]){
            return true;
        }
    }
    return false;
}

实现正确性分析 #

你的简化实现可以覆盖所有情况，本质上和标准解法完全等价，具体推导如下：

1. 循环范围完全一致 #

标准解法通过奇偶分支计算lastIndex，循环条件为i < lastIndex：

• 当数组长度n为偶数时，lastIndex = n/2，循环范围是i ∈ [0, n/2 - 1]
• 当n为奇数时，lastIndex = n/2 + 1，循环范围是i ∈ [0, n/2]

你的实现中lastIndex = n - (n/2 + 1)，循环条件为i <= lastIndex：

• 当n为偶数时，lastIndex = n/2 - 1，循环范围是i ∈ [0, n/2 - 1]，和标准解法偶数情况完全一致
• 当n为奇数时，lastIndex = n/2，循环范围是i ∈ [0, n/2]，和标准解法奇数情况完全一致

2. 判断条件等价 #

标准解法的判断条件是arr[i] == x && arr[i+n/2] == x，你的实现是array[i]==x && array[i]==array[i+array.length/2]，这两个逻辑完全等价：
若array[i] == x且array[i] == array[i+n/2]，则必然有array[i+n/2] == x；反之，若arr[i] == x且arr[i+n/2] == x，也能推出arr[i] == arr[i+n/2]。

综上，你的简化实现逻辑严谨，能够正确覆盖所有测试场景，且代码更简洁，省去了奇偶判断的分支逻辑。

内容的提问来源于stack exchange，提问作者Gargouri Nourallah