关于golang:Leetcode专题数组540有序数组中的单一元素

力扣链接：https://leetcode-cn.com/probl…
解题思路：

1. 首先，算法应该造就思维，看到有序数组以及题干要求的 logn 的解法，那么首先就应该想到的是二分查找，这算是解法的第一步
2. 找到算法的思路后，开始找法则，或者能够叫找公式。如数组：[1,1,2,3,3,4,4,8,8], 如果数组中没有单个数字，那么该数组就应该是 [1,1,2,2,3,3,4,4,8,8]; 能够找出的一个法则是：下标从 0 开始，到 len(nums) – 1 完结，下标为偶数的和下标为相邻奇数的数字相等。即：nums[0] == nums[1]; nums[2] == nums[3] ….
3. 找到第二点所示的法则后，因为咱们须要应用奇偶数下标来判断，那么 mid := (high – low) >> 1 + low，mid 可能是奇数，也可能是偶数，然而不管 mid 是奇数还是偶数，遵循的法则都是 nums[偶数] == nums[相邻的奇数]，基于这一点，当 mid 是奇数时，那么判断 nums[mid – 1] == nums[mid]; 如果相等，那么阐明只呈现一个的数字在右半局部，那么 low = mid + 1, 如果不相等，则证实只呈现一个的数字在左半局部，那么 high = mid，当 mid 是偶数时，比拟的是 nums[mid] 是否等于 nums[mid + 1]；如果相等，阐明单个数字在右半局部，如果不相等，阐明在左半局部
4. 通过下面的判断，能够晓得有两个分支：mid 是奇数和 mid 是偶数，每个分支下各自有是否跟相邻数字相等的判断，这里有另外一个优化的技巧，即异或，在查找单个数字的时候见识过异或的威力，实际上异或还有一个定律：奇数和 1 异或等于减一，偶数异或 1 等于加一；那么能够优化 if-else 分支，不必去分奇数偶数，只有相邻想等的，那么单个数在右半局部，不想等则在左半局部

func SingleNonDuplicate(nums []int) int {low, high := 0, len(nums) - 1
    for low < high {mid := (high - low) >> 1 + low
        if nums[mid] == nums[mid^1] {low = mid + 1} else {high = mid}
    }
    return nums[low]
}