O(lg n)复杂度查找有序非降数组中唯一重复元素的Java算法求解

本题要求时间复杂度为O(lg(n))，优先考虑二分查找方案，结合非降序数组的特性可按如下逻辑实现：

前提推导 #

• 非降序数组中，重复出现2次的元素必定相邻
• 结合题目唯一重复、数组长度为n的设定，符合该类算法题的通用隐含约束：数组元素取值范围为[1, n-1]，除重复元素外其余值连续不重复，因此对于无重复的子区间[left, right]，必然满足A[right] - A[left] == right - left（有序无重复整数的元素差值等于索引差值）
• 若上述等式不成立，说明当前子区间存在重复元素，可据此收缩二分区间

public class FindDuplicate {
    public static int findDuplicate(int[] A) {
        int left = 0;
        int right = A.length - 1;
        while (left < right) {
            // 计算mid避免整数溢出
            int mid = left + (right - left) / 2;
            // 检查mid位置是否和相邻元素重复，命中直接返回
            if (A[mid] == A[mid + 1]) {
                return A[mid];
            }
            if (mid > 0 && A[mid] == A[mid - 1]) {
                return A[mid];
            }
            // 判断左半区间是否存在重复
            if (A[mid] - A[left] == mid - left) {
                // 左半区间无重复，搜索右半区间
                left = mid + 1;
            } else {
                // 左半区间存在重复，搜索左半区间
                right = mid;
            }
        }
        // 边界情况：重复元素在左右边界重合位置
        return A[left];
    }

    public static void main(String[] args) {
        // 测试用例
        int[] test1 = {1,2,3,3,4,5};
        System.out.println(findDuplicate(test1)); // 输出3
        int[] test2 = {2,2,3,4,5,6};
        System.out.println(findDuplicate(test2)); // 输出2
        int[] test3 = {1,2,3,4,5,5};
        System.out.println(findDuplicate(test3)); // 输出5
    }
}

• 无额外数据结构使用，仅用到3个临时索引变量，空间复杂度为O(1)
• 每次二分将搜索区间缩小一半，时间复杂度严格满足O(lg(n))
• 提前判断mid位置的相邻元素，大部分场景下可以提前命中返回，减少迭代次数
• 没有使用任何Java内置的集合操作或查找函数，符合题目要求

内容的提问来源于stack exchange，提问作者FLY FOX 2058