Encuentra el número que falta en una array ordenada

Dada una lista de n-1 enteros y estos enteros están en el rango de 1 a n. No hay duplicados en la lista. Falta uno de los enteros en la lista. Escribe un código eficiente para encontrar el entero que falta. 

Ejemplos: 

Entrada: arr[] = [1, 2, 3, 4, 6, 7, 8]
Salida: 5

Entrada: arr[] = [1, 2, 3, 4, 5, 6, 8, 9]
Salida: 7

Enfoque ingenuo: una solución simple es aplicar los métodos discutidos para encontrar el elemento faltante en una array desordenada . La complejidad temporal de esta solución es O(n).

Enfoque eficiente: se basa en el algoritmo divide y vencerás que hemos visto en la búsqueda binaria, el concepto detrás de esta solución es que los elementos que aparecen antes del elemento faltante tendrán ar[i] – i = 1 y los que aparecen después del elemento faltante elemento tendrá ar[i] – i = 2.

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

// A binary search based program to find the
// only missing number in a sorted array of
// distinct elements within limited range.
#include <iostream>
using namespace std;
 
int search(int ar[], int size)
{
    // Extreme cases
    if (ar[0] != 1)
        return 1;
    if (ar[size - 1] != (size + 1))
        return size + 1;
 
    int a = 0, b = size - 1;
    int mid;
    while ((b - a) > 1) {
        mid = (a + b) / 2;
        if ((ar[a] - a) != (ar[mid] - mid))
            b = mid;
        else if ((ar[b] - b) != (ar[mid] - mid))
            a = mid;
    }
    return (ar[a] + 1);
}
 
int main()
{
    int ar[] = { 1, 2, 3, 4, 5, 6, 8 };
    int size = sizeof(ar) / sizeof(ar[0]);
    cout << "Missing number:" << search(ar, size);
}
 
// This code is contributed by Pushpesh Raj

// A binary search based program
// to find the only missing number
// in a sorted array of distinct
// elements within limited range.
import java.io.*;
 
class GFG {
    static int search(int ar[], int size)
    {
        // Extreme cases
        if (ar[0] != 1)
            return 1;
        if (ar[size - 1] != (size + 1))
            return size + 1;
 
        int a = 0, b = size - 1;
        int mid = 0;
        while ((b - a) > 1) {
            mid = (a + b) / 2;
            if ((ar[a] - a) != (ar[mid] - mid))
                b = mid;
            else if ((ar[b] - b) != (ar[mid] - mid))
                a = mid;
        }
        return (ar[a] + 1);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int ar[] = { 1, 2, 3, 4, 5, 6, 8 };
        int size = ar.length;
        System.out.println("Missing number: "
                           + search(ar, size));
    }
}
 
// This code is contributed
// by inder_verma.

# A binary search based program to find
# the only missing number in a sorted
# in a sorted array of distinct elements
# within limited range
 
 
def search(ar, size):
   # Extreme cases
    if(ar[0] != 1):
        return 1
    if(ar[size-1] != (size+1)):
        return size+1
 
    a = 0
    b = size - 1
    mid = 0
    while b > a + 1:
        mid = (a + b) // 2
        if (ar[a] - a) != (ar[mid] - mid):
            b = mid
        elif (ar[b] - b) != (ar[mid] - mid):
            a = mid
    return ar[a] + 1
 
 
# Driver Code
a = [1, 2, 3, 4, 5, 6, 8]
n = len(a)
 
print("Missing number:", search(a, n))
 
# This code is contributed
# by Mohit Kumar

// A binary search based program
// to find the only missing number
// in a sorted array of distinct
// elements within limited range.
using System;
 
class GFG {
    static int search(int[] ar, int size)
    {
        // Extreme cases
        if (ar[0] != 1)
            return 1;
        if (ar[size - 1] != (size + 1))
            return size + 1;
 
        int a = 0, b = size - 1;
        int mid = 0;
        while ((b - a) > 1) {
            mid = (a + b) / 2;
            if ((ar[a] - a) != (ar[mid] - mid))
                b = mid;
            else if ((ar[b] - b) != (ar[mid] - mid))
                a = mid;
        }
        return (ar[a] + 1);
    }
 
    // Driver Code
    static public void Main(String[] args)
    {
        int[] ar = { 1, 2, 3, 4, 5, 6, 8 };
        int size = ar.Length;
        Console.WriteLine("Missing number: "
                          + search(ar, size));
    }
}
 
// This code is contributed
// by Arnab Kundu

<?php
// A binary search based program to find the
// only missing number in a sorted array of
// distinct elements within limited range.
 
function search($ar, $size)
{
   //Extreme cases
    if($ar[0]!=1)
        return 1;
    if($ar[$size-1]!=($size+1))
        return $size+1;
   
    $a = 0;
    $b = $size - 1;
    $mid;
    while (($b - $a) > 1)
    {
        $mid = (int)(($a + $b) / 2);
        if (($ar[$a] - $a) != ($ar[$mid] -
                                   $mid))
            $b = $mid;
        else if (($ar[$b] - $b) != ($ar[$mid] -
                                        $mid))
            $a = $mid;
    }
    return ($ar[$a] + 1);
}
 
// Driver Code
$ar = array(1, 2, 3, 4, 5, 6, 8 );
$size = sizeof($ar);
echo "Missing number: ",
     search($ar, $size);
 
// This code is contributed by ajit.
?>

<script>
// A binary search based program
// to find the only missing number
// in a sorted array of distinct
// elements within limited range.
 
function findMissing(arr) {
  var size = arr.length;
 //Extreme cases
    if(ar[0]!=1)
        return 1;
    if(ar[size-1]!=(size+1))
        return size+1;
         
  var low = 0;
  var high = arr.length;
  while (low <= high) {
    var mid = Math.floor((low+high)/2);
    if ((arr[mid]-mid === 1) && (arr[mid+1]-(mid+1) === 2)) return arr[mid]+1;
    if (arr[mid]-mid === 1) {
      low = mid+1;
    } else {
      high = mid-1;
    }
  }
  return -1;
}
 
// Driver Code
 
let ar = [1, 2, 3, 4, 5, 6, 8];
document.write("Missing number: " +findMissing(ar));
 
// This code is contributed by mohit kumar 29.
</script>

Missing number:7

Complejidad de tiempo: O(log(N)), donde N es la longitud de la array dada
Espacio auxiliar: O(1)