{"post":"

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}\nOutput: 4

Input: {0, 1, 3, 4,5, 6, 7, 9}\nOutput: 2

# Algorithm

Initialize start and end indices for the array.
While start is less than or equal to end, do the following:\n
1. Calculate the mid index as the average of start and end.
2. If the mid element is not equal to the mid index, then the missing element is in the left subarray.\nSet end to mid - 1.
3. If the mid element is equal to the mid index, then the missing element is in the right subarray.\nSet start to mid + 1.
\n
If start is greater than end, then the missing element is start.

Code:

#include<iostream>\n#include<algorithm>\n\nusing namespace std;\n\nint smallest_missing(int arr[], int start, int end) {\n  if (start > end) {\n    return end + 1;\n  }\n\n  if (start != arr[start]) {\n    return start;\n  }\n\n  int mid = (start + end) / 2;\n\n  if (arr[mid] == mid) {\n    return smallest_missing(arr, mid + 1, end);\n  }\n\n  return smallest_missing(arr, start, mid);\n}\n\nint main() {\n  int arr[100], n, i;\n  cout << \"Enter number of elements: \";\n  cin >> n;\n  cout << \"\\nEnter elements: \";\n\n  for (i = 0; i < n; i++) {\n    cin >> arr[i];\n  }\n\n  cout << \"Original array: \";\n\n  for (int i = 0; i < n; i++) {\n    cout << arr[i] << \" \";\n  }\n\n  int answer;\n\n  answer = smallest_missing(arr, 0, n - 1);\n\n  cout << \"\\nSmallest missing element is \" << answer;\n\n  return 0;\n}\n\n

Output

Enter number of elements: 5\n\nEnter elements: 1 2 3 5 6\nOriginal array: 1 2 3 5 6\nSmallest missing element is 4\n\n

\n","title":"Program to find the smallest element missing in a sorted array in C++","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"description":"Learn how to find the smallest missing element in a sorted array in C++. The program uses a binary search algorithm to efficiently search for the missing element and returns the result in linear time. ","slug":"cpp/examples/program-to-find-smallest-element-missing-in-sorted-array-cpp/","articleId":"636a83417bb1ce5072622b3d","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}