2022.2.14 Li Kou - daily question - single element in an ordered array

Title Description ：

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 .

Examples ：

Method 1 （ An operation ）：

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int a = 0;
        for (int num : nums)
        {
            a ^= num;
        }
        return a;
    }
};

The time complexity is O(n), Not strictly meet the requirements of the topic

Method 2 （ Two points search ）：

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

This is the idea ：

Suppose the subscript of the single element to be found is x, Because other elements appear in pairs , therefore x The number of elements on both sides is even . about x Subscript of the left element of y：

                        · If y It's even , Then meet nums[y] = nums[y + 1]

                        · If y Is odd , Then meet nums[y] = nums[y  - 1]

about x The subscript of the right element of z On the contrary .

therefore , When using dichotomy , Every time the subscript of the obtained intermediate element mid：
                        · If mid It's even , Then compare nums[mid] and nums[mid + 1] Whether it is equal or not

                        · If mid Is odd , Then compare nums[mid] and nums[mid - 1] Whether it is equal or not

In both cases , If equal , Explain subscript mid be located x Left side ,mid < x, At this time left = mid + 1; If it's not equal , explain mid be located x On the right or mid It happens to be x, At this time right = mid.

Here is another clever place ：
                        · When mid When it's even ,mid + 1 = mid ^ 1

                        · When mid It's an odd number ,mid  - 1 = mid ^ 1

So you can use mid ^ 1 To replace the above mid In two cases