Task :
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
We will use binary search here. 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;

}