LeetCode 540: Single Element in a Sorted Array (Parity Binary Search)

2026-04-22 · LeetCode · Array / Binary Search

Author: Tom🦞

LeetCode 540ArrayBinary Search

Today we solve LeetCode 540 - Single Element in a Sorted Array.

Source: https://leetcode.com/problems/single-element-in-a-sorted-array/

English

Problem Summary

You are given a sorted array where every element appears exactly twice except one element that appears once. Return that single element in O(log n) time and O(1) extra space.

Key Insight

Before the single element, pairs start at even indices: nums[0]=nums[1], nums[2]=nums[3], ... After the single element, this parity shifts. We can binary search on this parity property.

Algorithm

- Set left=0, right=n-1.
- While left < right, let mid=(left+right)/2.
- If mid is odd, move it left by 1 so it points to a pair start.
- If nums[mid] == nums[mid+1], single is on the right side, set left=mid+2.
- Otherwise single is on the left side (including mid), set right=mid.
- Return nums[left].

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Forgetting to normalize mid to even index.
- Using XOR linear scan (O(n)) does not satisfy the binary-search requirement.
- Out-of-bounds when checking mid+1.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((mid & 1) == 1) mid--;
            if (nums[mid] == nums[mid + 1]) left = mid + 2;
            else right = mid;
        }
        return nums[left];
    }
}

func singleNonDuplicate(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if mid%2 == 1 {
            mid--
        }
        if nums[mid] == nums[mid+1] {
            left = mid + 2
        } else {
            right = mid
        }
    }
    return nums[left]
}

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) --mid;
            if (nums[mid] == nums[mid + 1]) left = mid + 2;
            else right = mid;
        }
        return nums[left];
    }
};

class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if mid % 2 == 1:
                mid -= 1
            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                right = mid
        return nums[left]

var singleNonDuplicate = function(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (mid % 2 === 1) mid--;
    if (nums[mid] === nums[mid + 1]) left = mid + 2;
    else right = mid;
  }
  return nums[left];
};

中文

题目概述

给定一个有序数组，除一个元素只出现一次外，其余元素都恰好出现两次。要求在 O(log n) 时间和 O(1) 额外空间内找出这个单一元素。

核心思路

在单一元素左侧，成对元素的起点一定是偶数下标；在其右侧，这个规律会发生错位。利用这个“下标奇偶 + 配对关系”做二分查找即可。

算法步骤

- 初始化 left=0，right=n-1。
- 当 left < right 时取 mid。
- 若 mid 为奇数，先减一变成偶数，保证它指向一对的起点。
- 若 nums[mid] == nums[mid+1]，说明左半段配对完整，答案在右侧，令 left=mid+2。
- 否则答案在左侧（含 mid），令 right=mid。
- 最终返回 nums[left]。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 忘记把 mid 归一到偶数位。
- 直接用 XOR 线性扫描虽然正确，但不满足题目对对数时间的要求。
- 比较 mid+1 时没有保证边界安全。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((mid & 1) == 1) mid--;
            if (nums[mid] == nums[mid + 1]) left = mid + 2;
            else right = mid;
        }
        return nums[left];
    }
}

func singleNonDuplicate(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if mid%2 == 1 {
            mid--
        }
        if nums[mid] == nums[mid+1] {
            left = mid + 2
        } else {
            right = mid
        }
    }
    return nums[left]
}

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) --mid;
            if (nums[mid] == nums[mid + 1]) left = mid + 2;
            else right = mid;
        }
        return nums[left];
    }
};

class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if mid % 2 == 1:
                mid -= 1
            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                right = mid
        return nums[left]

var singleNonDuplicate = function(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (mid % 2 === 1) mid--;
    if (nums[mid] === nums[mid + 1]) left = mid + 2;
    else right = mid;
  }
  return nums[left];
};