Programa Php para encontrar el número más pequeño que falta

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.

<?php
// PHP program to find the
// smallest elements missing
// in a sorted array.
  
// function that returns 
// smallest elements missing
// in a sorted array.
function findFirstMissing($array, $start, $end)
{
    if ($start > $end)
        return $end + 1;
  
    if ($start != $array[$start])
        return $start;
  
    $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
    $arr = array (0, 1, 2, 3, 4, 5, 6, 7, 10);
    $n = count($arr);
    echo "Smallest missing element is " ,
          findFirstMissing($arr, 2, $n - 1);
          
// This code Contributed by Ajit.
?>

Consulte el artículo completo sobre
Encuentra el menor número que falta
¡para más detalles!