Leetcode540：有序数组中的单一元素

题目描述：

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

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

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

代码思路：

这段代码的目的是在一个排序后的数组中找到唯一的非重复元素。这个数组有一个特殊的性质：除了一个元素之外，其他所有元素都是成对出现的。这段代码利用了二分查找的思想来高效地找到这个唯一的非重复元素。下面是代码的详细思路：

关键点：

• 由于数组是排序的，并且除了一个元素外其他元素都成对出现，所以可以通过比较中间元素和其后一个元素是否相同来确定搜索的方向。
• 调整 mid 到偶数索引是为了确保每次比较的都是成对元素中的第一个元素，从而正确判断非重复元素位于当前 mid 的左侧还是右侧。

• 代码实现：

  int singleNonDuplicate(int* nums, int numsSize) {
      int left=0;
      int right=numsSize-1;
      while (left < right) {
      int mid = (right + left) / 2;
      if (mid % 2 == 1) {  // 如果 mid 是奇数
          mid--;  // 调整 mid 为偶数
      }
      if (nums[mid] == nums[mid + 1]) {
          left = mid + 2;  // 单个元素在右侧
      } else {
          right = mid;  // 单个元素在左侧或就是 mid
      }
  }
      return nums[left];
  }