Find the only repeating element in a sorted array of size n | C ++ program to find the only repeating element in an array of size n and elements from range 1 to n - 1. ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findRepeatingElement ( int arr [ ] , int low , int high ) { if ( low > high ) return -1 ; int mid = low + ( high - low ) / 2 ; if ( arr [ mid ] != mid + 1 ) { if ( mid > 0 && arr [ mid ] == arr [ mid - 1 ] ) return mid ; return findRepeatingElement ( arr , low , mid - 1 ) ; } return findRepeatingElement ( arr , mid + 1 , high ) ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int index = findRepeatingElement ( arr , 0 , n - 1 ) ; if ( index != -1 ) cout << arr [ index ] ; return 0 ; }