Force buckle 540 A single element in an ordered array

subject

Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .

Example

Input : nums = [1,1,2,3,3,4,4,8,8]
Output : 2

Input : nums = [3,3,7,7,10,11,11]
Output : 10

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： An operation

Java Realization

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int ans = 0;
        for (int num : nums) {
    
            ans ^= num;
        }
        return ans;
    }
}

Method 2： Two points search

Java Realization

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int n = nums.length;
        int l = 0, r = n - 1;

        while (l < r) {
    
            int mid = l + r >> 1;
            if (mid % 2 == 0) {
    
                if (nums[mid] == nums[mid + 1]) l = mid + 1;
                else r = mid;
            } else {
    
                if (nums[mid] == nums[mid - 1]) l = mid + 1;
                else r = mid;
            }
        }
        return nums[l];
    }
}