Some examples:

`nums = [1, 1, 2, 3, 3 ,4, 4, 5, 5]`

If middle element is equal to its left, the single number exists in the left half (`right = mid`

).

`nums = [1, 1, 2, 2, 3, 3, 4, 5, 5]`

If middle element is equal to its right, the single number exists in the right half (`left = mid`

).

However, the above rules do not hold when we have

`nums = [1, 1, 2, 2, 3, 4, 4]`

The middle element is equal to its left, yet the single number exists in the right half (`left = mid + 1`

).

Similarly, if

`nums = [1, 1, 2, 3, 3, 4, 4]`

The middle element is equal to its right, yet the single number exists in the left half (`right = mid - 1`

).

Hence, when doing binary search, apart from what we need to in a normal binary search, we need to check `(right - left + 1) % 4`

. The rules are different when the remainder is 1 or 3.

```
class Solution(object):
def single_non_duplicate(self, nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if (right - left + 1) % 4 == 1:
if nums[mid] == nums[mid - 1]:
right = mid
elif nums[mid] == nums[mid + 1]:
left = mid
else:
# A number which is not equal to its left nor right
# is a single number.
return nums[mid]
else:
if nums[mid] == nums[mid - 1]:
left = mid + 1
elif nums[mid] == nums[mid + 1]:
right = mid - 1
else:
return nums[mid]
return nums[left]
```