Wednesday, March 20, 2013

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 

1 comment :

  1. the code is not working if i remove any number before the mid
    e.g 3

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top