﻿ Find a missing number in sorted number list ~ Programming Tutorials by SourceTricks
Wednesday, March 20, 2013

## Find a missing number in sorted number list

#### You are given a sorted number list from 0 to n. The list is missing one number, find out that number

We can run a binary search. Check the value in the middle, and see if the index of it is same as the value. If it is not, then 0 to mid range has a missing number, search in that range. Otherwise search in the range mid+1 to n. Continue similarly reducing the range by half every time, until you find the missing number.

```#include <iostream>

using namespace std;

int findMissing(int *input, int len)
{
int start = 0, end = len;
while (start < len) {
int mid = (start+end)/2;
if (input[mid] == mid ) {
if (input[mid+1] != mid+1) return mid+1;
start = mid+1;
} else {
if (input[mid-1] != mid-1) return mid-1;
end = mid;
}
}
return -1;
}

const int MAX_LEN = 15;

int main()
{
int input[MAX_LEN] = {0,1,2,3,4,5,6,7,8,9,10,12,13,14,15};
cout << "Missing number: " <<  findMissing(input,MAX_LEN) << endl;
return 0;
}```

Output:-
`Missing number: 11 `

Name

Email *

Message *