A dichotomy of Valentine's Day

Title Description

A single element in an ordered array

Topic ideas

   The key to this question is to realize that before individual elements appear , Because arrays are ordered , Two identical elements are arranged together , Observe the subscript to find ：

1 1 2 2 3 4 4
0 1 2 3 4 5 6

$$\begin{gathered} nums[y]==nums[y+1]\iff yyesaccidentallyCount \\ nums[y-1]==nums[y]\iff yyesp.Count \end{gathered}$$
   When individual elements appear , Yes ：
$$\begin{gathered} nums[z]==nums[z+1]\iff zyesp.Count \\ nums[z-1]==nums[z]\iff zyesaccidentallyCount \end{gathered}$$
   So we can use this property to dichotomy , Find the right endpoint satisfying the first property interval or the left endpoint satisfying the second property interval .

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) 
    {
    
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
    
        	/* Because the update is l = mid  So we need to add 1*/
            int mid = (l + r + 1) >> 1;
            if ((mid & 1) == 0)
            {
    
                if (mid > 0 && nums[mid - 1] == nums[mid]) 
                	r = mid - 1;
                else l = mid;
            }
            else
            {
    
                if (mid + 1 < n && nums[mid] == nums[mid + 1]) 
                	r = mid - 1;
                else l = mid;
            }
        }
        return nums[l];
    }
};

   This problem can be further optimized , Think about a bit operation Exclusive or , if x Is odd , be x ^ 1 = x - 1, if x It's even , be x ^ 1 = x, The two cases can be summed up by using XOR ：

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) 
    {
    
        // The key to this question lies in the single element x Before appearance 
        // if nums[y] == nums[y + 1]  be y Must be an even number 
        // In a single element x After a  
        // if nums[z] == nums[z + 1]  be z It must be odd 
        // You can use this property to dichotomy 
        // further   When mid It's an odd number  mid ^ 1 = mid - 1
        // When mid When it's even  mid ^ 1 = mid + 1
        // We find satisfaction nums[y] == nums[y + 1] <-> y For the even 
        //nums[y - 1] == nums[y] <-> y Is odd 
        // The right border of 
        // So we just need to compare nums[mid] == nums[mid ^ 1] Whether it is established or not   There is no need to discuss parity 
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
    
            int mid = (l + r) >> 1;
            /* If this property is satisfied   shows mid Still in the left section   In order to find the boundary   Give Way l = mid + 1*/
            /* There will be no cross-border   Because if mid be equal to 0  Exclusive or 1 still 0  And mid = (l + r) / 2 <= r mid + 1  Greater than r Will not be greater than n - 1 */
            if (nums[mid] == nums[mid ^ 1]) l = mid + 1;
            /* Otherwise, explain mid Not in the left section   to update r by mid*/
            else r = mid;
        }
        return nums[l];
    }
};

   You can also observe ：

1 1 2 2 3 4 4
0 1 2 3 4 5 6

   Because the left side of a single number is a pair of identical numbers , So the subscript of the number appearing alone must be even , Even subscripts can be bisected , keep mid The condition of being even is mid -= mid & 1,mid It's an odd number ,mid & 1 yes 1;mid When it's even ,mid & 1 yes 0.
   The first unsatisfied property nums[y] == nums[y + 1] The even subscript of is the answer .

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) 
    {
    
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
    
            int mid = (l + r) >> 1;
            mid -= (mid & 1);
            /* If the conditions are met   Then let l Two steps forward */
            if (mid + 1 < n && nums[mid] == nums[mid + 1])
                l = mid + 2;
            /* If not satisfied   Give Way r = mid  Control must be able to scan the answer */
            else r = mid;
        }
        return nums[r];
    }
};