Find the only repeating element in a sorted array of size n - GeeksforGeeks
Given a sorted array of n elements containing elements in range from 1 to n-1 i.e. one element occurs twice, the task is to find the repeating element in an array.
Read full article from Find the only repeating element in a sorted array of size n - GeeksforGeeks
Given a sorted array of n elements containing elements in range from 1 to n-1 i.e. one element occurs twice, the task is to find the repeating element in an array.
An efficient method is to use Binary Search .
1- Check if the middle element is the repeating one.
2- If not then check if the middle element is at proper position if yes then start searching repeating element in right.
3- Otherwise the repeating one will be in left.
1- Check if the middle element is the repeating one.
2- If not then check if the middle element is at proper position if yes then start searching repeating element in right.
3- Otherwise the repeating one will be in left.
int findRepeatingElement(int arr[], int low, int high){ // low = 0 , high = n-1; if (low > high) return -1; int mid = (low + high) / 2; // Check if the mid element is the repeating one if (arr[mid] != mid + 1) { if (mid > 0 && arr[mid]==arr[mid-1]) return mid; // If mid element is not at its position that means // the repeated element is in left return findRepeatingElement(arr, low, mid-1); } // If mid is at proper position then repeated one is in // right. return findRepeatingElement(arr, mid+1, high);}