Sign InCoursewareNuggetsTutorials AboutClassesCodePad

Find the Only Duplicate

Given a sorted list of n elements in the range from 1 to n-1 (only one element occurs twice), find the duplicate element.

For example:

list = [1, 2, 3, 4, 4, 5] 
result = 4

list = [1, 2, 2, 3, 4]
result = 2

Tip: Think about the value of the element and the relation to its position.

# Returns the index of the duplicate element in list from index low to high. # If no duplicate is found, returns -1. def find_duplicate(list, low, high): # base case if low >= high: return -1 # TODO: write your code here my_list = [1, 2, 3, 4, 4, 5] n = len(my_list) index = find_duplicate(my_list, 0, n-1) if (index >= 0): print(my_list[index])
© CS Wonders·About·Classes·Cheatsheet