#include <stdio.h>
 
// Function to find smallest missing element in a sorted
// array of distinct non-negative integers
int smallestMissing(int arr[], int low, int high)
{
    // base condition
    if (low > high)
        return low;
 
    int mid = low + (high - low) / 2;
 
    // if mid index matches with the mid element, then the mismatch
    // lies on the right half
    if (arr[mid] == mid)
        return smallestMissing(arr, mid + 1, high);
    else
        // mismatch lies on the left half
        return smallestMissing(arr, low, mid - 1);
}
 
// main function
int main(void)
{
    int arr[] = { 0, 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int low = 0, high = n - 1;
 
    printf("The smallest missing element is %d",
            smallestMissing(arr, low, high));
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGdW5jdGlvbiB0byBmaW5kIHNtYWxsZXN0IG1pc3NpbmcgZWxlbWVudCBpbiBhIHNvcnRlZAovLyBhcnJheSBvZiBkaXN0aW5jdCBub24tbmVnYXRpdmUgaW50ZWdlcnMKaW50IHNtYWxsZXN0TWlzc2luZyhpbnQgYXJyW10sIGludCBsb3csIGludCBoaWdoKQp7CiAgICAvLyBiYXNlIGNvbmRpdGlvbgogICAgaWYgKGxvdyA+IGhpZ2gpCiAgICAgICAgcmV0dXJuIGxvdzsKCiAgICBpbnQgbWlkID0gbG93ICsgKGhpZ2ggLSBsb3cpIC8gMjsKCiAgICAvLyBpZiBtaWQgaW5kZXggbWF0Y2hlcyB3aXRoIHRoZSBtaWQgZWxlbWVudCwgdGhlbiB0aGUgbWlzbWF0Y2gKICAgIC8vIGxpZXMgb24gdGhlIHJpZ2h0IGhhbGYKICAgIGlmIChhcnJbbWlkXSA9PSBtaWQpCiAgICAgICAgcmV0dXJuIHNtYWxsZXN0TWlzc2luZyhhcnIsIG1pZCArIDEsIGhpZ2gpOwogICAgZWxzZQogICAgICAgIC8vIG1pc21hdGNoIGxpZXMgb24gdGhlIGxlZnQgaGFsZgogICAgICAgIHJldHVybiBzbWFsbGVzdE1pc3NpbmcoYXJyLCBsb3csIG1pZCAtIDEpOwp9CgovLyBtYWluIGZ1bmN0aW9uCmludCBtYWluKHZvaWQpCnsKICAgIGludCBhcnJbXSA9IHsgMCwgMSwgMiwgMywgNCwgNSwgNiB9OwogICAgaW50IG4gPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKICAgIGludCBsb3cgPSAwLCBoaWdoID0gbiAtIDE7CgogICAgcHJpbnRmKCJUaGUgc21hbGxlc3QgbWlzc2luZyBlbGVtZW50IGlzICVkIiwKICAgICAgICAgICAgc21hbGxlc3RNaXNzaW5nKGFyciwgbG93LCBoaWdoKSk7CgogICAgcmV0dXJuIDA7Cn0=