RUN

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

Written By -

## 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, 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] << " ";

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

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

return 0;

}``````

Related Posts:

Tutorials

Examples

Online Compilers

Interview Questions

Recent Articles