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

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

Initialize start and end indices for the array.
While start is less than or equal to end, do the following:
1. Calculate the mid index as the average of start and end.
2. If the mid element is not equal to the mid index, then the missing element is in the left subarray. Set end to mid - 1.
3. If the mid element is equal to the mid index, then the missing element is in the right subarray. Set start to mid + 1.
If start is greater than end, then the missing element is start.

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;
}

Output

Enter number of elements: 5

Enter elements: 1 2 3 5 6
Original array: 1 2 3 5 6
Smallest missing element is 4