Missing number in sorted array

Missing number in sorted array

Given an array of sorted number of size N which contains numbers in range 1 to N-1, with some numbers missing. Find the smallest missing number in sorted array of integers. Example:

A = [1,2,3,5,7,8] Smallest missing number : 4
A = [1,2,3,4,6,8,10,11] Smallest missing number  : 5

Find smallest missing number in sorted array

What if there are numbers from 1 to N, and there are N slots and if numbers are sorted. In zero based indexed array, i will be stored at (i-1)th index.

What if one number is missing? Then every number i greater than missing number will be stored at i-2 index. Let’s use this property. We can use divide and conquer approach here. Start with middle element. If middle element is at proper location, it means all numbers less than mid are present in array and hence missing number cannot be in left part of array. Look in right portion of array. If middle element is not at its proper place, missing number is should be present in left part of array and is less than middle. So, we will look in left portion of array.

Termination condition will be if start of array is not at proper place or start becomes greater than end of the array. Implementation is given below:

#include <stdio.h>
 
int findSmallestMissingNumber(int a[], int start, int end){
	if(start < end){
		int mid  = (start + end)/2;
		if(a[mid] >  mid+1 )
			return findSmallestMissingNumber(a, start, mid);
		else
			return findSmallestMissingNumber(a, mid+1, end);
  	}
  	return start+1;
}
 
int main(void) {
 
	int a[] = {1,2,4,5,7,8};
	int size = sizeof(a)/sizeof(a[0]);
 
	printf("\nSmallest missing number : %d", 
                findSmallestMissingNumber(a,0,size-1));
 
	return 0;
}

Complexity of algorithm to find smallest element in array is O(log N). There is hidden space complexity associated with recursion. If n is very large number, it is preferable to use iterative implementation, as recursion may lead to stack overflow.

#include <stdio.h>

int findSmallestMissingNumber(int a[], int start, int end){

	while(start < end) {
		int mid = (start + end)/2;
		
		if(a[mid] > mid+1 ){
			end = mid;
		}
		else{
			start = mid+1;
		}
	}
 	return start+1;
}
 
int main(void) {
 
	int a[] = {2,3,4,5,6,7,8};
	int size = sizeof(a)/sizeof(a[0]);
 
	printf("\nSmallest missing number : %d", 
                findSmallestMissingNumber(a,0,size));
 
	return 0;
}

Please share if something is wrong or any other suggestion. Share if you liked the content. Sharing is caring.

  • Dc

    Theres an issue with the algorithm for finding duplicities in an array. Index can easily be out of bounds. Input array = {1, 2, 3, 1050} and you are trying to change array[1050] to its minus value.

    • http://algorithmsandme.in/ Jitendra Sangar

      Ah, sorry missed to mention that range of numbers is 0 to N-1 in this case also. Will correct it.