Missing and Duplicate numbers in a continuous list

Given a sorted array of continuous numbers, there is one number missing and another one occurring twice. Find the missing and duplicate.

Approach :- We iterate through the array. for each integer we check if the index is matching the number. There are 3 possible cases (when iterator is 3):
1. 0,1,2,3,4,5 continues
2. 0,1,2,4,5,6 found missing
3. 0,1,2,7,3,5 found duplicate

Note down if you found a missing or duplicate. If you found a missing, then next numbers are 1+. And if you found duplicate, next numbers are 1-. So we use delta to keep track of that when we continue to find the other entity. When we found both the entities we break the loop.

Solution:

#include <iostream>

using namespace std;

void findMissingAndDuplicate(int *input,int *missing, int *duplicate,int len)
{
    int delta = 0;
    bool foundMissing = false, foundDuplicate = false;

    for(int i=0;i<len;i++) {
        if(!foundMissing && (input[i] == i+delta+1)) {
            *missing = i+delta;
            delta += 1;
            foundMissing =true;
            if (foundDuplicate)
                break;
        } else if (!foundDuplicate && (input[i] != i+delta)) {
            *duplicate = input[i];
            foundDuplicate = true;
            if (foundMissing)
                break;
            delta -= 1;
        }
    }
}

const int MAX_LEN = 16;

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

Output:-

Missing number: 11 and duplicate: 3

Other option is to first find only the missing number. Then do a summation of all the numbers and subtract the sum of numbers minus the missing number. Conversely, find the duplicate number first and then apply the sum trick to find out the missing.

Binary search is not possible. But a divide and conquer method can be applied, but it gets messier. Below is an attempt to do this (not complete code).

#include <iostream>

using namespace std;

// find a missing in the given range
void findMissing(int *input,int *missing, int start, int len)
{
}

// find a duplicate in the given range
bool findDuplicate(int *input,int *duplicate, int start, int len)
{
}

// For a given missing find the duplicate in the given range!
bool findDuplicateNormal(int *input,int *missing, int *duplicate, int start, int len)
{
}

// return: 0 - not found : 1 - miss found : 2 - duplicate found : 3 both found.
// values 1 and 2 become irrevalant as they never happen.
int findMissingAndDuplicate(int *input,int *missing, int *duplicate, int start, int len)
{
    int mid = start + (len / 2);
    if (input[mid] == mid) { // duplicate and miss are either in the first half - caseA
        // duplicate and miss are either in the second half. caseB
        // or miss in 2nd half and duplicate on both caseC
        // neither miss nor duplicate caseD
        int ret = findMissingAndDuplicate(input,missing, duplicate, start, len);
        switch (ret) {
        case 0: // none found --> caseB, caseC, caseD
            findMiss(input,missing,mid,len/2);
            bool retDupFound =  findDuplicate(input,missing,mid,len/2);
            if (!retDupFound) { // it is duplicate on both case! --> caseC
                bool localDupFound = findDuplicateNormal(input, missing, duplicate, start, len);
                if (!localDupFound) // caseD!
                    return 0;
            }
            return 3;
            break;
        case 1: // found missing. This should not occur!
            break;
        case 2: // found duplicate. This should not occur!
            break;
        case 3: // both are found --> caseA
            return 3;
        }
    } else if (input[mid] < mid) { // duplicate in 1st half and miss in 2nd half
        findDuplicate(input,duplicate,start, len/2);
        findMiss(input,missing,mid,len/2);
        return 3;
    } else { // miss in 1st half and duplicate on both --> caseE
        // miss in 1st half and duplicate in 2nd half --> caseF
        findMiss(input, missing, mid, len/2);
        int retDupFound = findDuplicate(input,duplicate,start, len/2);
        if (!retDupFound) { // it is duplicate on both case! caseE
            findDuplicateNormal(input, missing, duplicate, start, len);
        }
        return 3; // applicable for both caseE or caseF
    }
    return 0;
}

const int MAX_LEN = 16;

int main()
{
          int input[MAX_LEN] = {0,1,2,3,4,5,3,6,7,8,9,10,12,13,14,15}; // duplicate in 1st half, miss in 2nd

    int missing, duplicate;
    findMissingAndDuplicate(input,&missing, &duplicate,MAX_LEN);
    cout << "Missing number: " << missing << " and duplicate: " << duplicate  << endl;
    return 0;
}