540. Single Element in a Sorted Array 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if ((mid & 1) == 0) {
                // mid 为偶数索引
                if (nums[mid] == nums[mid + 1]) {
                    left = mid + 2;
                } else {
                    right = mid;
                }
            } else {
                // mid 为奇数索引
                if (nums[mid] == nums[mid - 1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }

        return nums[left];
    }
}

Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int singleNonDuplicate(int[] nums) {
        // nums:  [1, 1, 2, 3, 3, 4, 4, 8, 8]
        // index: [0, 1, 2, 3, 4, 5, 6, 7, 8]

        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            // 整合了 mid 为偶数和奇数的情况，如果 mid 为偶数，则与右侧元素比较，如果 mid 为奇数，则与左侧元素比较
            if (nums[mid] == nums[mid ^ 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

References

540. Single Element in a Sorted Array
剑指 Offer II 070. 排序数组中只出现一次的数字