Given a sorted array of consecutive numbers from to , find the first missing number, i.e., the hole.
The naive approach is to linearly traverse the array to find the element that is not one greater than its predecessor:
This solution has a time complexity. A more optimized algorithm uses the binary search algorithm to solve the problem in time. However, this exploits the fact that the array is sorted and consists of consecutive numbers starting from .
Since we know that we have a sorted array, the value of any given element (until we reach the missing element) should be equal to its index + . Using that, we can implement a binary search algorithm. If the middle element of the array has a value equal to its index + , search over the right array; otherwise, search over the left array.
#include <iostream>using namespace std;int findMissing(int arr[], int N){int left = 0, right = N - 1;while (left <= right) {int mid = (left + right) / 2;// If the middle element is not on// the middle index, then the missing element is mid + 1.if (arr[mid] != mid + 1 && arr[mid - 1] == mid){return mid + 1;}// This case means that the missing element is// not to the left. So search the right.if (arr[mid] == mid + 1)left = mid + 1;// This case means that the missing element is not// to the right. So search the left.elseright = mid - 1;}// Will reach here if no missing element found.return -1;}// Driver codeint main(){int arr[] = {1,3,4,5,6,7,8};int size = sizeof(arr)/sizeof(arr[0]);cout << "The missing element is: " << findMissing(arr, size);return 0;}