Home » Interview » Array Interview Questions » Find smallest missing number in a sorted array

# Find smallest missing number in a sorted array

## Find the smallest missing number in N sized sorted array having unique elements in the range of 0 to M-1, where M>N

Example:

Input: [0,1,2,3,4,6,7,8,9] → output: 5

Input: [0,1,2,4,5,6,7,8] → output: 3

Input: [0,1,2,3,4,5,6,8,9] → output: 7

Input: [0,1,2,3,4,5,7,8,9] → output: 6

## ALGORITHM 1

TIME COMPLEXITY – O(N)

SPACE COMPLEXITY – O(1)

Linear Search, simply comparing the index and the array element if it is greater than, that number is missing.

Example:

Apply algorithm on Input array, ### Program for Algorithm 1

```#include <bits/stdc++.h>
using namespace std;

int main()
{
int M = 11;
int arr[] = {0,1,2,3,4,5,8,9,10};
int N = sizeof(arr)/sizeof(arr);

for(int i=0;i<N;i++)
{
if(arr[i] > i) //if array element is greater than i then that element is missing number.
{
cout<<"Missing element is "<<i<<endl;
return 0;
}
}

cout<<"Element "<<N<<" is missing\n";
return 0;
}```

## ALGORITHM 2

TIME COMPLEXITY – O(MlogN), M is range of elements and N is size of array

SPACE COMPLEXITY – O(1)

1. Run a loop from 0 to M-1 and do
2. Binary search for each element in the range and see if the number exists or not.
3. [0,1,2,4,5,6,7,8] is the given array so, here range is 0 to 8. Binary  search for every number from 0 to 8 in the array.
4. Print the element which is missing first, it will be the smallest missing element.

Example:

Input array:

 0 1 2 4 5

Apply algorithm on Input array,

M = 5,

For i = 0,

Binary Search(0,input array) = True

For i = 1,

Binary Search(1,input array) = True

For i = 2,

Binary Search(2,input array) = True

For i = 3,

Binary Search(3,input array) = False

Therefore, smallest missing element is = 3

### Program for Algorithm 2

```#include <bits/stdc++.h>
using namespace std;

// code for searching element is present in array or not
//using binary search
bool binary_search_missing(int arr[],int low,int high,int x)
{

if(low > high)
return false;

int mid = low + (high - low)/2;
if(arr[mid]==x)
return true;

else if(arr[mid] > x)
return binary_search_missing(arr,low,mid-1,x);
else
return binary_search_missing(arr,mid+1,high,x);

}

int main()
{

int M = 11;
int arr[] = {0,1,2,3,4,5,8,9,10};
int N = sizeof(arr)/sizeof(arr);
for(int i=0;i<M;i++)
{
if(!binary_search_missing(arr,0,N,i))// if binary_search return false we print the element
{
cout<<"Element "<<i<<" is missing\n";
return 0;
}
}

cout<<"Element "<<M<<" is missing\n";
return 0;
}```