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
C++
// C++ program to find the smallest elements
// missing in a sorted array.
#include<bits/stdc++.h>
using namespace std;
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 code
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Smallest missing element is " <<
findFirstMissing(arr, 0, n-1) << endl;
}
// This code is contributed by
// Shivi_Aggarwal
C
// C program to find the smallest elements missing
// in a sorted array.
#include<stdio.h>
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 above function
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Smallest missing element is %d",
findFirstMissing(arr, 0, n-1));
return 0;
}
Java
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));
}
}
Python3
# 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
C#
// C# program to find the smallest
// elements missing in a sorted array.
using System;
class GFG
{
static 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()
{
int []arr = {0, 1, 2, 3, 4, 5, 6, 7, 10};
int n = arr.Length;
Console.Write("smallest Missing element is : "
+ findFirstMissing(arr, 0, n - 1));
}
}
// This code is contributed by Sam007
PHP
<?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.
?>
Javascript
<script>
// Javascript program to find the smallest
// elements missing in a sorted array.
function findFirstMissing(array, start, end)
{
if (start > end)
return end + 1;
if (start != array[start])
return start;
let mid = parseInt((start + end) / 2, 10);
// Left half has all elements from 0 to mid
if (array[mid] == mid)
return findFirstMissing(array, mid+1, end);
return findFirstMissing(array, start, mid);
}
let arr = [0, 1, 2, 3, 4, 5, 6, 7, 10];
let n = arr.length;
document.write("smallest Missing element is " +
findFirstMissing(arr, 0, n - 1));
</script>
C++
//C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Program to find missing element
int findFirstMissing(vector<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 po*/
if (arr[mid] != mid+first)
return findFirstMissing(arr, start,
mid , first);
else
return findFirstMissing(arr, mid + 1,
end , first);
}
return start + first;
}
// Program to find Smallest
// Missing in Sorted Array
int findSmallestMissinginSortedArray(vector<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.size() - 1] == arr.size() - 1)
return arr.size();
int first = arr[0];
return findFirstMissing(arr, 0, arr.size() - 1, first);
}
// Driver program to test the above function
int main()
{
vector<int> arr = {0, 1, 2, 3, 4, 5, 7};
int n = arr.size();
// Function Call
cout<<"First Missing element is : "<<findSmallestMissinginSortedArray(arr);
}
// This code is contributed by mohit kumar 29.
Java
// 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));
}
}
Python3
# 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
C#
// C# program for above approach
using System;
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 code
static public void Main ()
{
GFG small = new GFG();
int[] arr = {0, 1, 2, 3, 4, 5, 7};
int n = arr.Length;
// Function Call
Console.WriteLine("First Missing element is : " +
small.findSmallestMissinginSortedArray(arr));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
// Program to find missing element
function findFirstMissing(arr, start, end, first)
{
if (start < end)
{
let mid = (start + end) / 2;
/** Index matches with value
at that index, means missing
element cannot be upto that po*/
if (arr[mid] != mid + first)
return findFirstMissing(arr, start,
mid, first);
else
return findFirstMissing(arr, mid + 1,
end, first);
}
return start + first;
}
// Program to find Smallest
// Missing in Sorted Array
function 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[arr.length - 1] == arr.length - 1)
return arr.length;
let first = arr[0];
return findFirstMissing(
arr, 0, arr.length - 1, first);
}
// Driver code
let arr = [ 0, 1, 2, 3, 4, 5, 7 ];
let n = arr.length;
// Function Call
document.write("First Missing element is : " +
findSmallestMissinginSortedArray(arr));
// This code is contributed by Mayank Tyagi
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA