Find the first missing element in a sorted array

Problem Statement

Given a sorted array containing distinct non-negative integers. Find the first missing element.

Example Test Case 1

Array: 0 1 2 3 4 6
Output: 5
Explanation: 5 is the first missing number which should be there in the array.

Example Test Case 2

Array: 1 2 3 4 5 6
Output: 0
Explanation: Since the array can contain non-negative integers, the first missing element will be 0.

Example Test Case 3

Array: 0 1 2 3 4 5 6
Output: 7
Explanation: The first missing number is 7 which should be there in the array.

Solution

Since the array is sorted and contains only distinct non-negative integers, for each position i before the missing number, arr[i] = i. The first number which doesn’t satisfy the above constraint my answer.

Consequently, any given array can be divided into two parts:

1. Part A: This is the part where all the numbers are present. It always starts with zero as the first element. If the part A ends at position i, then i + 1 will be my answer. (see example test case 1).
2. Part B: This is the part from where at least one number goes missing.

In any given array, either of the three cases can happen :

1. Case 1: Length of part A = 0 and length of part B > 0. In this case, the answer will be 0 (example test case 2)
2. Case 2: Length of part A > 0 and length of part B = 0. In this case, the missing number will be last number of array + 1 (example test case 3).
3. Case 3: Length of part A > 0 and length of part B > 0. In this case, if the part A ends at position i, then i + 1 will be my answer. (example test case 1).

In all the three cases, we just have to calculate the ending position of part A, which can be done by modifying the standard binary search algorithm as shown below:

Implementation

#include <iostream>
#include <vector>
using namespace std;

// Returns the last valid position in the vector vec.
int findPos(vector<int>& vec) {
	int lo = 0, hi = vec.size() - 1;
	int mid = lo + (hi - lo)/2;

	int lastPos = -1;
	while (lo <= hi) {
		mid = lo + (hi - lo)/2;	
		if (vec[mid] == mid) {
			lastPos = mid;
			lo = mid + 1;
		}
		else {
			hi = mid - 1;
		}
	}
	return lastPos;
}

int main() {
	vector<int> vec = { 0, 1, 2, 3, 5 };
	int pos = findPos(vec);
	cout << pos + 1 << "\n";
}

Time Complexity

The total time complexity of the solution will be same as binary search ie. O(log(n)).