# Python binary search: easy to understand

• 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]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.