Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

missing number
sorted
array
algorithm

How to find the missing number in a sorted array

Educative Answers Team

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

svg viewer

This solution has a O(n)O(n) time complexity. A more optimized algorithm uses the binary search algorithm to solve the problem in O(logn)O(log n) time. However, this exploits the fact that the array is sorted and consists of consecutive numbers starting from 11.

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 + 11. Using that, we can implement a binary search algorithm. If the middle element of the array has a value equal to its index + 11, 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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring