####
** 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

the code is not working if i remove any number before the mid

ReplyDeletee.g 3

ReplyDeletesac louis vuittonmichael kors outlet onlineugg clearancechristian louboutin salebeats headphoneschristian louboutin pas cherralph lauren polo outletcanada goose coatslongchamp handbagsugg boots clearance2016.12.29xukaimin

ReplyDeletedesigner handbagstoms shoeslouboutin uktrue religion outletcoach outletlongchamp bagsugg saleyeezy boost 350wholesale nike shoescoach factory outlet20170111

This should be the working code

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

end = mid;

}

}

return -1;

}