```
func singleNonDuplicate(nums []int) int {
piv := pickPiv(nums)
return singleRecur(nums, piv)
}
func pickPiv(nums []int) int {
if len(nums) < 3 {
return 0;
}
piv := int(len(nums) / 2)
//if we pick a pivot between a pair, increment.
//We don't want to split the array between pairs.
if nums[piv] == nums[piv+1] {
return piv+1;
} else {
return piv;
}
}
func singleRecur(nums []int, piv int) int {
if len(nums) == 0 {
return 0;
}
if len(nums) < 3 {
return nums[0];
}
//this is our base case of three numbers. There are three possibilities:
//a) [2,1,1] in this case, nums[0] is our non-dup
//b) [1,1,2] in this case, nums[2] is our non-dup
//c) [1,2,3] in this case, nums[1] is between two other pairs, so nums[1] is our non-dup.
//For example, the full array for case (c) might look like this: [1,1,2,3,3]
if len(nums) == 3 {
if nums[1] == nums[2] {
return nums[0];
} else if nums[1] == nums[0] {
return nums[2];
} else {
return nums[1];
}
}
left := nums[:piv+1]
right := nums[piv+1:]
//since a side without duplications contains only pairs, its length is a multiple of two.
//Therefore, whichever side has an odd length must contain our non-dup.
if len(left) % 2 != 0 {
piv = pickPiv(left)
return singleRecur(left, piv)
} else {
piv = pickPiv(right)
return singleRecur(right, piv)
}
}
```