有序数组中出现一次的元素

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param v int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4c67fc80c37649ac906fee76ec82beb4?tpId=196&tqId=40508&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        left, right = 0, len(v) - 1
        当left < right时，二分查找res:
            mid = left + (right - left) / 2
            如果v[mid] != v[left] and v[mid] != v[right]：
                return v[mid]
            否则，如果v[mid] == v[mid - 1]：
                    若(mid + 1) % 2 == 0: # 解在区间[mid + 1, right]
                        left = mid + 1
                    否则：
                        right = mid - 2
            否则： #  v[mid] == v[mid + 1]
                若mid % 2 == 0：# 解在区间[mid + 2, right]
                    left = mid + 2
                否则：
                    right = mid - 1
    复杂度：
        时间复杂度：O(logN)
        空间复杂度：O(1)
    """

    def singleElement(self, v):
        # write code here
        left, right = 0, len(v) - 1

        while left < right:
            mid = left + (right - left) / 2
            if v[mid] != v[mid - 1] and v[mid] != v[mid + 1]:
                return v[mid]
            elif v[mid] == v[mid - 1]:
                if (mid + 1) % 2 == 0:  # 解在区间[mid + 1, right]
                    left = mid + 1
                else:
                    right = mid - 2
            else:  # v[mid] == v[mid + 1]
                if mid % 2 == 0:  # 解在区间[mid + 2, right]
                    left = mid + 2
                else:
                    right = mid - 1

        return v[left]


if __name__ == "__main__":
    sol = Solution()

    # nums = [1, 2, 2, 3, 3]

    # nums = [1, 1, 5, 5, 8, 8, 9, 10, 10]

    nums = [5, 5, 6, 6, 9, 10, 10, 11, 11, 13, 13, 14, 14]

    res = sol.singleElement(nums)

    print res