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])