Related Tags

missing number
sorted
array
algorithm

# How to find the missing number in a sorted array

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.

## Code

#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