C C++ JAVA PYTHON SQL HTML CSS DSA Robotics AWS CODING INTERVIEW PREPARATION

Made with  & Code

# 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:

Online Compilers