有序数组中的单一元素

题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

思想

折半查找，计算当前值与前后值得大小关系，得到单一元素存在的区间。时间复杂度为 O(log n)，空间复杂度为 O(1)。

示例

public int singleNonDuplicate(int[] nums, int p, int q) {
    if (p == q) return nums[p];
    int mid = (p + q) / 2, key = nums[mid], m = nums[mid - 1], n = nums[mid + 1];
    if (m != key && n != key) return key;
    boolean flag = (mid - p + 1) % 2 == 0;
    if (flag) {
        if (m == key) p = mid + 1;
        else q = mid - 1;
    } else {
        if (m == key) q = mid - 2;
        else p = mid + 2;
    }
    return singleNonDuplicate(nums, p, q);
}