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

  1.     public int singleNonDuplicate(int[] nums) {
  2.         // 单数的下标一定是偶数，比如11233中2的下标是2
  3.         // 如果存在偶数i，那么在单数的左侧，nums[i]==num[i+1]，在单数及其右侧，nums[i]!=num[i+1]
  4.         int low = 0;
  5.         int high = nums.length - 1;
  6.         while (low < high) {
  7.             int mid = low + (high - low) / 2;
  8.             mid -= mid & 1; // 确保mid是偶数
  9.             if (nums[mid] == nums[mid + 1]) { // 偶数位置的元素和相邻的下一个元素相等
  10.                 low = mid + 2; // 说明单数在nums[mid+1]的右边
  11.             } else { // 不相等，则说明单数在nums[mid]的左边，或者单数就是nums[mid]
  12.                 high = mid;
  13.             }
  14.         }
  15.         return nums[low];
  16.     }