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

# Python3 program to find the smallest
# elements missing in a sorted array.
  
def findFirstMissing(array, start, end):
  
    if (start > end):
        return end + 1
  
    if (start != array[start]):
        return start;
  
    mid = int((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 program to test above function
arr = [0, 1, 2, 3, 4, 5, 6, 7, 10]
n = len(arr)
print("Smallest missing element is",
      findFirstMissing(arr, 0, n-1))
  
# This code is contributed by Smitha Dinesh Semwal 

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:

# Python3 program for above approach 
  
# Function to find Smallest 
# Missing in Sorted Array
def 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[-1] == len(arr) - 1):
        return len(arr)
      
    first = arr[0]
      
    return findFirstMissing(arr, 0, 
            len(arr) - 1, first)
  
# Function to find missing element 
def findFirstMissing(arr, start, end, first):
      
    if (start < end):
        mid = int((start + end) / 2)
          
        # Index matches with value 
        # at that index, means missing 
        # element cannot be upto that point 
        if (arr[mid] != mid + first):
            return findFirstMissing(arr, start,
                                    mid, first)
        else:
            return findFirstMissing(arr, mid + 1, 
                                    end, first)
      
    return start + first
  
# Driver code
arr = [ 0, 1, 2, 3, 4, 5, 7 ]
n = len(arr)
  
# Function Call 
print("First Missing element is :",
    findSmallestMissinginSortedArray(arr))
  
# This code is contributed by rag2127

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!