Encuentre el único elemento repetido en una array ordenada de tamaño n

Dada una array ordenada de n elementos que contienen elementos en el rango de 1 a n-1, es decir, un elemento aparece dos veces, la tarea es encontrar el elemento repetido en una array.

Ejemplos: 

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

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

Un enfoque ingenuo es escanear toda la array y verificar si un elemento aparece dos veces y luego regresar. Este enfoque requiere tiempo O(n).

Un método eficiente es utilizar la búsqueda binaria .

Observación: si un elemento ‘X’ se repite, entonces debe estar en el índice ‘X’ de la array. Entonces el problema se reduce a encontrar cualquier elemento cuyo valor sea el mismo que su índice.

// C++ program to find the only repeating element in an
// array of size n and elements from range 1 to n-1.
#include <bits/stdc++.h>
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 size){
    int lo = 0;
    int hi = size - 1;
    int mid;
     
    while(lo <= hi){
        mid = (lo+hi)/2;
         
        if(arr[mid] <= mid){
            hi = mid-1;
        }
        else{
            lo = mid + 1;
        }
    }
     
    return lo;
}
 
// Driver code
int main()
{
    int arr[] = {1, 2, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = FindRepeatingElement(arr, n);
    if (index != -1)
        cout << arr[index];
    return 0;
}

// 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 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# 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
// PHP 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.
function findRepeatingElement($arr,
                              $low,
                              $high)
{
    // low = 0 , high = n-1;
    if ($low > $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.
?>

<script>
      // JavaScript 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.
      function findRepeatingElement(arr, low, high)
      {
       
        // low = 0 , high = n-1;
        if (low > high) return -1;
 
        var mid = parseInt((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
      var arr = [1, 2, 3, 3, 4, 5];
      var n = arr.length;
      var index = findRepeatingElement(arr, 0, n - 1);
      if (index != -1) document.write(arr[index]);
       
      // This code is contributed by rdtank.
    </script>

3

Complejidad de tiempo: O (log n)

Este artículo es una contribución de Sahil Chhabra (KILLER) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.