Trusted answers to developer questions

Educative Answers Team

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. else right = mid - 1; } // Will reach here if no missing element found. return -1; } // Driver code int 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; }

RELATED TAGS

missing number

sorted

array

algorithm

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses