C++ program to find the smallest element missing in a sorted array

Given: An array of integers having no duplicates. We have to find one of the integers is missing in the array.

Example:

Input: {0, 1, 2, 3, 5, 6, 7}
Output: 4

Input: {0, 1, 3, 4,5, 6, 7, 9}
Output: 2

# Algorithm

1. We will use binary search here.
2. Compare the mid index with mid element. If both are same then the missing element is there in the right sub array else missing element is in left subarray.

Code:

#include<iostream>
#include<algorithm>
using namespace std;

int smallest_missing(int arr[], int start, int end){
  if (start > end)
    return end + 1;

  if (start != arr[start])
    return start;

  int mid = (start + end) / 2;

  if (arr[mid] == mid)
    return smallest_missing(arr, mid + 1, end);

  return smallest_missing(arr, start, mid);
}

int main(){

  int arr[100], n, i;
  cout << "Enter number of elements: ";
  cin >> n;
  cout << "\nEnter elements: ";

  for (i = 0; i < n; i++)
    cin >> arr[i];

  cout << "Original array: ";

  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";

  int answer;

  answer = smallest_missing(arr, 0, n - 1);

  cout << "\nSmallest missing element is " << answer;

  return 0;

}

Report Error/ Suggestion

Related Posts:

• Diamond pattern program in C++
• 2’s complement in C++
• Swap two numbers using pointers
• Program to Shutdown and restart in C++
• Pattern Programs in C