LeetCode540——有序数组中的单一元素（二分法）

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例:

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10

题目分析

这次是用二分法的思想，你会发现下标 i（i是偶数）的数与 i+1（i+1是奇数），在遇到出现一次的数之前都是 nums[i] == nums[i+1] ， 在出现一次数的右边， nums[i] ！= nums[i+1] ，我们可以通过这一点进行二分查找。

代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l < r)
        {
            int mid = l + (r-l)/2;
            if(mid % 2 == 1)
            {
                mid--; //防止mid是奇数，如果是奇数则左移一位
            }
            if(nums[mid] == nums[mid+1])
            {
                l=mid+2; //说明目标在[mid+2,h]
            }
            else
            {
                r=mid; //否则目标在[l,mid]
            }
        }
        return nums[l];
    }
};