# Find the only repeating element in a sorted array of size n

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.

Examples :

```Input :  arr[] = { 1, 2 , 3 , 4 , 4}
Output :  4

Input :  arr[] = { 1 , 1 , 2 , 3 , 4}
Output :  1
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A naive approach is to scan the whole array and check if an element occurs twice, then return. This approach takes O(n) time.

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.

## C/C++

 `// C++ program to find the only repeating element in an ` `// array of size n and elements from range 1 to n-1. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns index of second appearance of a repeating element ` `// The function assumes that array elements are in range from ` `// 1 to n-1. ` `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); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int`  `arr[] = {1, 2, 3, 3, 4, 5}; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` `    ``int` `index = findRepeatingElement(arr, 0, n-1); ` `    ``if` `(index != -1) ` `        ``cout << arr[index]; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find the only repeating element in an ` `// array of size n and elements from range 1 to n-1. ` ` `  `class` `Test ` `{ ` `    ``// Returns index of second appearance of a repeating element ` `    ``// The function assumes that array elements are in range from ` `    ``// 1 to n-1. ` `    ``static` `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); ` `    ``} ` `     `  `    ``// Driver method ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int`  `arr[] = {``1``, ``2``, ``3``, ``3``, ``4``, ``5``}; ` `        ``int` `index = findRepeatingElement(arr, ``0``, arr.length-``1``); ` `        ``if` `(index != -``1``) ` `            ``System.out.println(arr[index]); ` `    ``} ` `} `

## Python

 `# Python 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. ` `def` `findRepeatingElement(arr, low, high): ` ` `  `    ``# low = 0 , high = n-1 ` `    ``if` `low > high: ` `        ``return` `-``1` ` `  `    ``mid ``=` `(low ``+` `high) ``/` `2` ` `  `    ``# Check if the mid element is the repeating one ` `    ``if` `(arr[mid] !``=` `mid ``+` `1``): ` `     `  `        ``if` `(mid > ``0` `and` `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) ` ` `  `# Driver code ` `arr ``=` `[``1``, ``2``, ``3``, ``3``, ``4``, ``5``] ` `n ``=` `len``(arr) ` `index ``=` `findRepeatingElement(arr, ``0``, n``-``1``) ` `if` `(index ``is` `not` `-``1``): ` `    ``print` `arr[index] ` ` `  `#This code is contributed by Afzal Ansari `

## C#

 `// C# program to find the only repeating ` `// element in an array of size n and  ` `// elements from range 1 to n-1. ` `using` `System; ` ` `  `class` `Test ` `{ ` `    ``// Returns index of second appearance of a ` `    ``// repeating element. The function assumes that ` `    ``// array elements are in range from 1 to n-1. ` `    ``static` `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); ` `    ``} ` `     `  `    ``// Driver method ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``int` `[]arr = {1, 2, 3, 3, 4, 5}; ` `        ``int` `index = findRepeatingElement(arr, 0, arr.Length-1); ` `        ``if` `(index != -1) ` `        ``Console.Write(arr[index]); ` `    ``} ` `} ` ` `  `// This code is contributed by Nitin Mittal. `

## PHP

 ` ``\$high``) ` `        ``return` `-1; ` ` `  `    ``\$mid` `= ``floor``((``\$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``); ` `} ` ` `  `// Driver code ` `\$arr` `= ``array``(1, 2, 3, 3, 4, 5); ` `\$n` `= sizeof(``\$arr``); ` `\$index` `= findRepeatingElement(``\$arr``, 0,  ` `                              ``\$n` `- 1); ` `if` `(``\$index` `!= -1) ` `echo` `\$arr``[``\$index``]; ` ` `  `// This code is contributed ` `// by nitin mittal.  ` `?> `

Output :

```3
```

Time Complexity : O(log n)