El elemento más pequeño mayor que X no está presente en la array

Dada una array arr[] de tamaño N y un entero X . La tarea es encontrar el elemento más pequeño mayor que X que no está presente en la array.
Ejemplos: 
 

Entrada: arr[] = {1, 5, 10, 4, 7}, X = 4 
Salida: 6 
6 es el número más pequeño mayor que 4 
que no está presente en la array.
Entrada: arr[] = {1, 5, 10, 6, 11}, X = 10 
Salida: 12  

Enfoque: Una solución eficiente se basa en la búsqueda binaria . Primero ordena la array. Tome bajo como cero y alto como N – 1 . Y busque el elemento X + 1. Si el elemento en el medio (que es (bajo + alto)/ 2) es menor o igual al elemento de búsqueda, haga bajo como medio + 1 . De lo contrario, haga alto como medio – 1 . Si el elemento en el medio es igual al elemento de búsqueda, entonces incremente el elemento de búsqueda en uno y hágalo alto como N – 1 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the smallest element greater
// than x which is not present in a[]
int Next_greater(int a[], int n, int x)
{
 
    // Sort the array
    sort(a, a + n);
 
    int low = 0, high = n - 1, ans = x + 1;
 
    // Continue until low is less
    // than or equals to high
    while (low <= high) {
 
        // Find mid
        int mid = (low + high) / 2;
 
        // If element at mid is less than
        // or equals to searching element
        if (a[mid] <= ans) {
 
            // If mid is equals
            // to searching element
            if (a[mid] == ans) {
 
                // Increment searching element
                ans++;
 
                // Make high as N - 1
                high = n - 1;
            }
 
            // Make low as mid + 1
            low = mid + 1;
        }
 
        // Make high as mid - 1
        else
            high = mid - 1;
    }
 
    // Return the next greater element
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 1, 5, 10, 4, 7 }, x = 4;
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << Next_greater(a, n, x);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the smallest element greater
// than x which is not present in a[]
static int Next_greater(int a[], int n, int x)
{
 
    // Sort the array
    Arrays.sort(a);
 
    int low = 0, high = n - 1, ans = x + 1;
 
    // Continue until low is less
    // than or equals to high
    while (low <= high)
    {
 
        // Find mid
        int mid = (low + high) / 2;
 
        // If element at mid is less than
        // or equals to searching element
        if (a[mid] <= ans)
        {
 
            // If mid is equals
            // to searching element
            if (a[mid] == ans)
            {
 
                // Increment searching element
                ans++;
 
                // Make high as N - 1
                high = n - 1;
            }
 
            // Make low as mid + 1
            low = mid + 1;
        }
 
        // Make high as mid - 1
        else
            high = mid - 1;
    }
 
    // Return the next greater element
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 5, 10, 4, 7 }, x = 4;
    int n = a.length;
 
    System.out.println(Next_greater(a, n, x));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function to return the smallest element
# greater than x which is not present in a[]
def Next_greater(a, n, x):
 
    # Sort the array
    a = sorted(a)
 
    low, high, ans = 0, n - 1, x + 1
 
    # Continue until low is less
    # than or equals to high
    while (low <= high):
 
        # Find mid
        mid = (low + high) // 2
 
        # If element at mid is less than
        # or equals to searching element
        if (a[mid] <= ans):
 
            # If mid is equals
            # to searching element
            if (a[mid] == ans):
 
                # Increment searching element
                ans += 1
 
                # Make high as N - 1
                high = n - 1
 
            # Make low as mid + 1
            low = mid + 1
 
        # Make high as mid - 1
        else:
            high = mid - 1
 
    # Return the next greater element
    return ans
 
# Driver code
a = [1, 5, 10, 4, 7]
x = 4
n = len(a)
 
print(Next_greater(a, n, x))
 
# This code is contributed
# by Mohit Kumar

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to return the smallest element greater
// than x which is not present in a[]
static int Next_greater(int []a, int n, int x)
{
 
    // Sort the array
    Array.Sort(a);
 
    int low = 0, high = n - 1, ans = x + 1;
 
    // Continue until low is less
    // than or equals to high
    while (low <= high)
    {
 
        // Find mid
        int mid = (low + high) / 2;
 
        // If element at mid is less than
        // or equals to searching element
        if (a[mid] <= ans)
        {
 
            // If mid is equals
            // to searching element
            if (a[mid] == ans)
            {
 
                // Increment searching element
                ans++;
 
                // Make high as N - 1
                high = n - 1;
            }
 
            // Make low as mid + 1
            low = mid + 1;
        }
 
        // Make high as mid - 1
        else
            high = mid - 1;
    }
 
    // Return the next greater element
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 5, 10, 4, 7 };
    int x = 4;
    int n = a.Length;
 
    Console.WriteLine(Next_greater(a, n, x));
}
}
 
// This code is contributed by Princi Singh

<?php
// PHP implementation of the approach
 
// Function to return the smallest element greater
// than x which is not present in a[]
function Next_greater($a, $n, $x)
{
 
    // Sort the array
    sort($a);
 
    $low = 0;
    $high = $n - 1;
    $ans = $x + 1;
 
    // Continue until low is less
    // than or equals to high
    while ($low <= $high)
    {
 
        // Find mid
        $mid = ($low + $high) / 2;
 
        // If element at mid is less than
        // or equals to searching element
        if ($a[$mid] <= $ans)
        {
 
            // If mid is equals
            // to searching element
            if ($a[$mid] == $ans)
            {
 
                // Increment searching element
                $ans++;
 
                // Make high as N - 1
                $high = $n - 1;
            }
 
            // Make low as mid + 1
            $low = $mid + 1;
        }
 
        // Make high as mid - 1
        else
            $high = $mid - 1;
    }
 
    // Return the next greater element
    return $ans;
}
 
// Driver code
$a = array( 1, 5, 10, 4, 7 );
$x = 4;
$n = count($a);
 
echo Next_greater($a, $n, $x);
 
// This code is contributed by Naman_garg.
?>

<script>
 
// Js implementation of the approach
 
// Function to return the smallest element greater
// than x which is not present in a[]
function Next_greater( a, n, x){
    // Sort the array
    a.sort(function(aa, bb){return aa - bb});
 
    let low = 0, high = n - 1, ans = x + 1;
 
    // Continue until low is less
    // than or equals to high
    while (low <= high) {
 
        // Find mid
        let mid = Math.floor((low + high) / 2);
 
        // If element at mid is less than
        // or equals to searching element
        if (a[mid] <= ans) {
 
            // If mid is equals
            // to searching element
            if (a[mid] == ans) {
 
                // Increment searching element
                ans++;
 
                // Make high as N - 1
                high = n - 1;
            }
 
            // Make low as mid + 1
            low = mid + 1;
        }
 
        // Make high as mid - 1
        else
            high = mid - 1;
    }
 
    // Return the next greater element
    return ans;
}
 
// Driver code
let a = [ 1, 5, 10, 4, 7 ]
let x = 4;
let n = a.length;
 
document.write( Next_greater(a, n, x));
</script>

6