287. Find the Duplicate Number

"""
Though the values are not ordered, the indices are still ordered. That's why binary search can still be used. Very interesting solution.
https://leetcode.com/problems/find-the-duplicate-number/discuss/72844/Two-Solutions-(with-explanation):-O(nlog(n))-and-O(n)-time-O(1)-space-without-changing-the-input-array
"""
class Solution:
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            cont = 0
            for num in nums:
                if num <= mid:
                    cont += 1

            if cont <= mid:
                left = mid + 1
            else:
                right = mid

        return right