Python binary search: easy to understand


  • 0
    N

    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]
    

Log in to reply
 

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