Find the smallest missing number in an array in C++

In this tutorial, we are going to learn how to find the smallest missing number in an array in C++. We can solve this problem either by using a linear search or by using binary search.

If we use a linear search to solve this problem then we have to iterate the array and when we find the difference between consecutive array elements to be greater then 1, we will print that number+1.

For example:

Let the array be:

1->2->4->5->6

Here, we start traversing the array and at index 1 and 2 the difference is greater than 1. So we will print the number at index 1 + 1. Let us try to use first linear search then we will solve the problem by binary search as well.

Program to find the smallest missing number in an array using Linear search in C++

Cpp Source code:

// Program to find the smallest missing number in an array using Linear search
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cout<<"Enter array length: ";
  cin>>n;
  cout<<"\nEnter array elements:\n";
  int arr[n];
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  cout<<"\nThe required smallest number is ";
  for(int i=0;i<n-1;i++)
  {
    if(arr[i+1]-arr[i]>1)
    {
      cout<<arr[i]+1<<"\n";
      break;
    }
  }
  return 0;
}

Input/output:

Enter array length: 5

Enter array elements:
1 2 4 5 6

The required smallest number is 3

Now we will solve this problem using binary search.

Program to find the smallest missing number in an array using Binary search in C++

Cpp source code:

// Program to find the smallest missing number in an array using Binary search
#include<bits/stdc++.h>
using namespace std;

int findFirstMissing(int array[], int start , int end){
    
    if(end<=start+1){
        return (start+1);
    }
    else{
        
        int mid = start + (end-start)/2;
        
        if((array[mid] - array[start]) != (mid-start))
            return findFirstMissing(array, start, mid);
        else
            return findFirstMissing(array, mid+1, end);
        
    }
}

// Driver Program
int main()
{
  int arr[] = {1,2,4,5,6};
  int n = sizeof(arr)/sizeof(arr[0]);
  cout<<"Smallest missing element is "<<findFirstMissing(arr, 0, n-1);
  return 0;
}

Input/Output:

Smallest missing element is 3

• Time complexity by using linear search is O(n).
• Time complexity by using binary search is O(n*log n).

You may also learn,

How the Bubble Sorting technique is implemented in Python

Heap Sort in C++

Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.