Programa Javascript 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.

<script>
  
    // Javascript program to find the smallest
    // elements missing in a sorted array.
      
    function findFirstMissing(array, start, end) 
    {
        if (start > end)
            return end + 1;
    
        if (start != array[start])
            return start;
    
        let mid = parseInt((start + end) / 2, 10);
    
        // Left half has all elements from 0 to mid
        if (array[mid] == mid)
            return findFirstMissing(array, mid+1, end);
    
        return findFirstMissing(array, start, mid);
    }
      
    let arr = [0, 1, 2, 3, 4, 5, 6, 7, 10];
    let n = arr.length;
  
    document.write("smallest Missing element is " + 
    findFirstMissing(arr, 0, n - 1));
      
</script>

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:

<script>
  
// Javascript program for the above approach
  
// Program to find missing element
function findFirstMissing(arr, start, end, first)
{
    if (start < end)
    {
        let 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
function findSmallestMissinginSortedArray(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.length - 1] == arr.length - 1)
        return arr.length;
      
    let first = arr[0];
      
    return findFirstMissing(
        arr, 0, arr.length - 1, first);
}
  
// Driver code
let arr = [ 0, 1, 2, 3, 4, 5, 7 ];
let n = arr.length;
  
// Function Call
document.write("First Missing element is : " + 
     findSmallestMissinginSortedArray(arr));
  
// This code is contributed by Mayank Tyagi
  
</script>

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!