前言
每天和你一起刷 LeetCode 每日一题~
LeetCode 启动！
题目：有序数组中的单一元素
代码与解题思路
先读题：
“一个仅由整数组成的有序数组”
“你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。”
看到这里基本上就能看出来题目要求我们用二分来做这道题目了，这题也是一道经典题目，在题目没给有序以及复杂度要求的时候，直接模拟，用哈希，或者用异或都可以很轻松的解答
怎么用二分做这道题呢？
核心思路：
“有一个数只会出现一次”
我们可以看到，示例一：[1,1,2,3,3,4,4,8,8]
在只出现一次的数字出现之前，偶数下标和下一个奇数下标的元素是相同的，而在特殊数字出现之后，偶数下标和下一个奇数下标的元素就不相同的了
很显然，该数组具有单调性，元素相同证明特殊数字在左区间，元素不相同证明特殊数字在右区间
最后一个问题，怎么样做到每次二分的是偶数下标？让二分上界 / 2，在取到 mid 之后让 mid * 2 这样得到就一定是偶数的下标了~
代码如下：
func singleNonDuplicate(nums []int) int {
l, r := 0, len(nums)/2
for l < r {
mid := (l+r)/2
if nums[mid*2] != nums[mid*2+1] {
r = mid
} else {
l = mid + 1
}
}
return nums[l*2]
}