有序数组的单一元素

题目

来源：力扣（LeetCode）
链接：有序数组的单一元素

分析

为了分析方便，始终控制折半查找的子区间长度为奇数。
设子区间为[left,right]
mid=left+(right-left)/2
mid将子区间分为两个区间有如下几种情况：

• 因为重复出现的元素两两配对，若[left,mid-1]区间长度为偶数
  • 若nums[mid] ==numd[mid-1]，则说明单一元素下标一定在$[left,mid-2]$[left,mid−2]中，且这一子区间长度为奇数。如子序列112334455中 $nums[mid]=numd[mid-1]=3$nums[mid]=numd[mid−1]=3，单一元素在左半区间。
  • 若nums[mid]==nums[mid+1],则说明单一元素一定在右半区间中,为保证右半区间长度为奇数，则left=mid+2如子序列112233455中 $nums[mid]=numd[mid+1]=3$nums[mid]=numd[mid+1]=3，单一元素在右半区间。
  • 若nums[mid]!=nums[mid+1]&&nums[mid]!=nums[mid-1]则返回nums[mid]
• 若[left,mid-1]区间长度为奇数，
  • 若 nums[mid]==nums[mid-1]，则说明单一元素一定在右半区间中.为保证右半区间长度为奇数，则更新left=mid+1。如子序列1122344中 $nums[mid]=numd[mid-1]=2$nums[mid]=numd[mid−1]=2，单一元素在右半区间。
  • 若nums[mid]==nums[mid+1]，则说明单一元素一定在左半区间中.为保证左半区间长度为奇数，则更新right=mid-1。如子序列1123344中 $nums[mid]=numd[mid-1]=3$nums[mid]=numd[mid−1]=3，单一元素在左半区间。
  • 若nums[mid]!=nums[mid+1]&&nums[mid]!=nums[mid-1]则返回nums[mid]

代码

int singleNonDuplicate(int* nums, int numsSize){
    if(numsSize==1) return nums[0];
    int left=0;
    int right=numsSize-1;
    int mid=0;
    
    while(left<right){
        mid=left+(right-left)/2;
        if(mid==0||mid==numsSize-1||nums[mid]!=nums[mid+1]&&nums[mid]!=nums[mid-1])
            return nums[mid];        
        int len=mid-left;
        if((len)%2==0){
            if(nums[mid]==nums[mid-1])
                right=mid-2;//保证子区间nums[left]~nums[right]长度为奇数
            else
                left=mid+2;
        }else{
            if(nums[mid]==nums[mid-1])
                left=mid+1;
            else 
                right=mid-1; 
        }
    }
    return nums[left];
}