Programa en C++ para encontrar el número faltante más pequeño

Dada una array ordenada de n enteros distintos donde cada entero está en el rango de 0 a m-1 y m > n. Encuentra el número más pequeño que falta en la array. 

Ejemplos 

Input: {0, 1, 2, 6, 9}, n = 5, m = 10 
Output: 3

Input: {4, 5, 10, 11}, n = 4, m = 12 
Output: 0

Input: {0, 1, 2, 3}, n = 4, m = 5 
Output: 4

Input: {0, 1, 2, 3, 4, 5, 6, 7, 10}, n = 9, m = 11 
Output: 8

Gracias a Ravichandra por sugerir seguir dos métodos.

Método 1 (Usar búsqueda binaria ) 
Para i = 0 a m-1, realice una búsqueda binaria de i en la array. Si i no está presente en la array, devuelva i.
Complejidad del tiempo: O(m log n) 

Método 2 ( búsqueda lineal ) 
Si arr[0] no es 0, devuelve 0. De lo contrario, recorra la array de entrada a partir del índice 0, y para cada par de elementos a[i] y a[i+1], encuentre la diferencia entre a ellos. si la diferencia es mayor que 1, entonces a[i]+1 es el número que falta. 
Complejidad de tiempo: O(n)

Método 3 (Usar búsqueda binaria modificada) 
Gracias a Yasein y Jams por sugerir este método. 
En el proceso de búsqueda binaria estándar, el elemento a buscar se compara con el elemento del medio y, en función del resultado de la comparación, decidimos si la búsqueda ha terminado o si vamos a la mitad izquierda o derecha. 
En este método, modificamos el algoritmo de búsqueda binaria estándar para comparar el elemento central con su índice y tomar una decisión sobre la base de esta comparación.

• Si el primer elemento no es el mismo que su índice, devuelva el primer índice
• De lo contrario, obtenga el índice medio, digamos medio
  • Si arr[mid] es mayor que mid, entonces el elemento requerido se encuentra en la mitad izquierda.
  • De lo contrario, el elemento requerido se encuentra en la mitad derecha.

// C++ program to find the smallest elements
// missing in a sorted array.
#include<bits/stdc++.h>
using namespace std;
  
int findFirstMissing(int array[], 
                    int start, int end)
{
    if (start > end)
        return end + 1;
  
    if (start != array[start])
        return start;
  
    int mid = (start + end) / 2;
  
    // Left half has all elements 
    // from 0 to mid
    if (array[mid] == mid)
        return findFirstMissing(array, 
                            mid+1, end);
  
    return findFirstMissing(array, start, mid);
}
  
// Driver code
int main()
{
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Smallest missing element is " <<
        findFirstMissing(arr, 0, n-1) << endl;
}
  
// This code is contributed by
// Shivi_Aggarwal 

Smallest missing element is 8

Nota: este método no funciona si hay elementos duplicados en la array.
Complejidad de tiempo: O (Iniciar sesión)

Otro método: la idea es usar la búsqueda binaria recursiva para encontrar el número faltante más pequeño. A continuación se muestra la ilustración con la ayuda de los pasos:

• Si el primer elemento de la array no es 0, entonces el número faltante más pequeño es 0.
• Si los últimos elementos de la array son N-1, entonces el número faltante más pequeño es N.
• De lo contrario, busque el elemento central del primer y último índice y verifique si el elemento central es igual al elemento deseado. es decir, primero + índice_medio.
  • Si el elemento del medio es el elemento deseado, entonces el elemento faltante más pequeño está en el espacio de búsqueda derecho del medio.
  • De lo contrario, el número faltante más pequeño está en el espacio de búsqueda izquierdo del medio.

A continuación se muestra la implementación del enfoque anterior:

//C++ program for the above approach
#include <bits/stdc++.h>
  
using namespace std;
  
// Program to find missing element
int findFirstMissing(vector<int> arr , int start ,
                        int  end,int first)
{
  
  if (start < end)
  {
    int mid = (start + end) / 2;
  
    /** Index matches with value
      at that index, means missing
      element cannot be upto that po*/
    if (arr[mid] != mid+first)
      return findFirstMissing(arr, start,
                                 mid , first);
    else
      return findFirstMissing(arr, mid + 1,
                                 end , first);
  }
  return start + first;
  
}
  
// Program to find Smallest
// Missing in Sorted Array
int findSmallestMissinginSortedArray(vector<int> arr)
{
    
  // Check if 0 is missing
  // in the array
  if(arr[0] != 0)
    return 0;
  
  // Check is all numbers 0 to n - 1
  // are present in array
  if(arr[arr.size() - 1] == arr.size() - 1)
    return arr.size();
  
  int first = arr[0];
  
  return findFirstMissing(arr, 0, arr.size() - 1, first);
}
  
  
// Driver program to test the above function
int main()
{
    vector<int> arr = {0, 1, 2, 3, 4, 5, 7};
    int n = arr.size();
  
    // Function Call
    cout<<"First Missing element is : "<<findSmallestMissinginSortedArray(arr);
}
  
// This code is contributed by mohit kumar 29.

First Missing element is : 6

Complejidad de tiempo: O (Iniciar sesión) 

Consulte el artículo completo sobre ¡ Encuentre el número faltante más pequeño para obtener más detalles!