Find the Duplicate Number

    def findDuplicate(self, nums):
        size = len(nums)
        i, j = 1, 1+size
        while i <= j:
            mid = (i+j)//2
            x = y = 0
            for num in nums:
                if num < mid:
                    x += 1
                elif num == mid:
                    y += 1
                    if y > 1:
                        return mid
            if x > mid - 1:
                j = mid - 1
            else:
                i = mid + 1