Home Â» Technical Interview Questions Â» 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

## Approach 1 for Find Smallest Missing Number in a Sorted Array

Here we just simply comparing the index and the array element if the array element is greater than, that number(i) is missing. Now move to the implementation using c++ language.

### C++ Program

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
if(a[i]>i)
{
cout<<i<<endl;
return 0;
}
}
cout<<n<<endl;
return 0;
}```
```9 11
0 1 2 3 4 5 8 9 10```
`6`

### Complexity Analysis for Find Smallest Missing Number in a Sorted Array

Time Complexity â€“ O(N) where n represents the size of the array. Here we traverse the array and once we find the answer then print it and return.

Space Complexity â€“ O(1) because we don’t use any auxiliary space here.

## Approach 2 for Find Smallest Missing Number in a Sorted Array

Here we use the concept of binary search because the array is already sorted. Here we search for each value of i in the range from 0 to M. If the element not found then print that element and return.

READ  Count Pairs Whose Products Exist in Array

### Algorithm

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.

### Explanation

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

### C++ Program for Find Smallest Missing Number in a Sorted Array

```#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 n,m;
cin>>n>>m;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<m;i++)
{
if(!binary_search_missing(a,0,n,i))
{
cout<<i;
return 0;
}
}
cout<<m;
return 0;
}```
```9 15
0 1 2 3 4 5 6 7 8```
`9`

### Complexity Analysis

Time Complexity â€“ O(MlogN) where M is a range of elements and N is the size of the array. Here we search for every value of i in the range 0 to M then it leads us to O(mlogn) time complexity.

Space Complexity â€“ O(1) because we don’t use any auxiliary space here.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions