**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**

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

Report Error/ Suggestion