540_有序数组中的单一元素

难度：中等

题目

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例

示例一：

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

示例二：

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

提示

• $1 <= nums.length <= 10^5$
• $0 <= nums[i] <= 10^5$

解题

根据题目要求，时间复杂度为O(log n)，首先想到二分法

当为偶数下标时，如果它和它的下一个相同，则说明出现一次的数在后半段，否则出现在前半段。

所以定义 left 和 right，在计算 mid 的时候，可以用 left + ( right - left ) / 2 来替代 ( left + right ) / 2以防止整数溢出。

public int singleNonDuplicate(int[] nums) {
  int n = nums.length;
  int left = 0,right = n-1,mid=0;
  while (left<right){
    mid = left+(right-left)/2;
    if (mid%2==1){
      // 如果mid为奇数
      mid--;
    }
    if (nums[mid]==nums[mid+1]){
      left = mid + 2;
    }else {
      right = mid;
    }
  }
  return nums[left];
}