def search_for_duplicated_value(sequence):
    """
    Using a varient of the binary search. Note that it does not return the first duplicate value 
    but one of the duplicate values.

    O(nlogn) - time
    O(1) - space
    """

    floor = 0
    ceiling = len(sequence) - 1

    while floor < ceiling:

        mid = floor + ((ceiling - floor) // 2)
        lower_floor, lower_ceiling = floor, mid
        higher_floor, higher_ceiling = mid + 1, ceiling

        # find the total number of numbers in lower range
        num_items_in_lower = 0
        for number in sequence:
            if lower_floor <= number <= lower_ceiling:
                num_items_in_lower += 1

        # find the total possible number in lower range
        distinct_possible_integers_in_lower = lower_ceiling - lower_floor + 1

        # based on this refine your search
        if num_items_in_lower > distinct_possible_integers_in_lower:
            floor, ceiling = lower_floor, lower_ceiling
        else:
            floor, ceiling = higher_floor, higher_ceiling

    return floor