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