Find the only repeating element in a sorted array of size n | Returns index of second appearance of a repeating element The function assumes that array elements are in range from 1 to n - 1. ; low = 0 , high = n - 1 ; Check if the mid element is the repeating one ; If mid element is not at its position that means the repeated element is in left ; If mid is at proper position then repeated one is in right . ; Driver code
def findRepeatingElement ( arr , low , high ) : NEW_LINE INDENT if low > high : NEW_LINE INDENT return - 1 NEW_LINE DEDENT mid = ( low + high ) / 2 NEW_LINE if ( arr [ mid ] != mid + 1 ) : NEW_LINE INDENT if ( mid > 0 and arr [ mid ] == arr [ mid - 1 ] ) : NEW_LINE INDENT return mid NEW_LINE DEDENT return findRepeatingElement ( arr , low , mid - 1 ) NEW_LINE DEDENT return findRepeatingElement ( arr , mid + 1 , high ) NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE index = findRepeatingElement ( arr , 0 , n - 1 ) NEW_LINE if ( index is not - 1 ) : NEW_LINE INDENT print arr [ index ] NEW_LINE DEDENT