2N+1数组只有一个单个元素，成对元素连续

def bs(arr):
    """
    arr: 2N + 1 数组, 只有一个元素单个，其他成对连续出现
    """
    # 成对出现，异或 ^，O（N）；成对连续出现，根据奇偶性二分
    left, right = 0, len(arr) - 1
    while left < right:
        mid = left + (right - left) // 2
        if mid - 1 >= left and mid + 1 <= right and arr[mid] != arr[mid - 1] and arr[mid] != arr[mid + 1]:
            return mid, arr[mid]
        elif mid + 1 <= right and arr[mid] == arr[mid + 1]:
            length = mid + 1 - left + 1
            if length % 2 == 1:
                right = mid - 1 # mid = mid + 1 且为 mid + 1 左边长度为奇数, right -> mid - 1
            else: 
                left = mid + 2  # mid = mid + 1 且为 mid + 1 右边长度为奇数, right -> mid + 2
                # left = mid
        elif mid - 1 >= left and arr[mid] == arr[mid - 1]:
            length = mid - left + 1
            if length % 2 == 1:
                right = mid - 2 # mid - 1 = mid 且为 mid 左边长度为奇数, right -> mid -2
            else:
                left = mid + 1 # mid - 1 = mid 且为mid 右边长度为奇数, right -> mid + 1
    # left = right
    # 【1，2，2】&nbs***bsp;【1，1，2】的情况
    return left, arr[left]

arr = [1,1,4,4,4,4,5,5,5,3,3,1,1]
arr = [1,1,2,2,5]
print(bs(arr))