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; 
} 

How to find the missing number in a sorted array

Given a sorted array of consecutive numbers from 111 to NNN, 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: 