LeetCode|LeetCode_二分搜索_中等_540.有序数组中的单一元素 leetcode|二分搜索|算法刷题

1.题目
2.思路
3.代码实现（Java）

1.题目给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1：
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2：
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-element-in-a-sorted-array
2.思路（1）二分搜索
思路参考该 LeedCode 用户题解。
题目要求算法的时间复杂度为 O(logn)，所以首先想到二分搜索，但是关键在于如何对数组 nums 进行二分。
【LeetCode|LeetCode_二分搜索_中等_540.有序数组中的单一元素】① 由题目可知，有序数组中每个元素都会出现两次，唯有一个数只会出现一次，以数组 [1, 1, 2, 3, 3, 4, 4, 8, 8] 为例，元素 2 只出现了一次；
② 如果将元素 2 去掉，那么数组中的所有元素均出现了2 次，并且可以组成 4 个相等数对：[1, 1]、[3, 3]、[4, 4]、[8, 8]，但是 2 的出现，破坏了原来的相等数对（并且数组长度也由偶数变成了奇数）：[1, 1]、[2 3]、[3, 4]、[4, 8]、[8, ]；
③ 此时我们可以发现：元素 2 之前的相等数对仍然存在，而之后的相等数对被破坏，所以我们将这一点作为二分的依据！
3.代码实现（Java）

//思路1————二分搜索 class Solution { public int singleNonDuplicate(int[] nums) { int length = nums.length; int left = 0; int right = length / 2; while (left < right) { int mid = (left + right) / 2; int index = mid * 2; if (nums[index] != nums[index + 1]) { //当前数对的两个元素不相等，故只出现一次的数在左边 right = mid; } else { //当前数对的两个元素相等，故只出现一次的数在右边 left = mid + 1; } } return nums[left * 2]; } }