Given a sorted array of consecutive numbers from $1$ to $N$, 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 $O(n)$ time complexity. A more optimized algorithm uses the *binary search* algorithm to solve the problem in $O(log n)$ time. However, this exploits the fact that the array is sorted and consists of consecutive numbers starting from $1$.

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 + $1$. Using that, we can implement a binary search algorithm. If the middle element of the array has a value equal to its index + $1$, 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;}

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS