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

class SmallestMissing 
{
    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 program to test the above function
    public static void main(String[] args) 
    {
        SmallestMissing small = new SmallestMissing();
        int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};
        int n = arr.length;
        System.out.println("First Missing element is : "
                + small.findFirstMissing(arr, 0, n - 1));
    }
}

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:

// Java Program for above approach
import java.io.*;
  
class GFG 
{
  
    // Program to find Smallest 
    // Missing in Sorted Array
    int findSmallestMissinginSortedArray(
                            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.length-1] == arr.length - 1)
        return arr.length;
      
    int first = arr[0];
  
    return findFirstMissing(arr,0,
                    arr.length-1,first);
    }
      
    // Program to find missing element 
    int findFirstMissing(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 point */
        if (arr[mid] != mid+first)
        return findFirstMissing(arr, start, 
                                    mid , first);
        else
        return findFirstMissing(arr, mid+1, 
                                    end , first);
    }
    return start+first;
  
    }
  
    // Driver program to test the above function
    public static void main(String[] args) 
    {
        GFG small = new GFG();
        int arr[] = {0, 1, 2, 3, 4, 5, 7};
        int n = arr.length;
          
        // Function Call
        System.out.println("First Missing element is : "
            + small.findSmallestMissinginSortedArray(arr));
    }
}

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!