Suppose you have a long list of numbers, which increases by 1 for each item in the list, ie: 1, 2, 3, 4, 5. Now suppose an element is missing from the list, say, 3. Now the list is: 1, 2, 4, 5. Now consider a list that is millions of elements long. How do you find the missing element without painstakingly iterating through the entire list in O(n) time? Simple: binary search it (with modifications) to achieve O(log(n)) time.

/*******************************************************************************
 * @file: find.c
 * @author: Matthew Giassa <matthew@giassa.net>
 * Test to check for a missing element in a sorted, strictly monotonically
 * increasing data set.
 ******************************************************************************/


/*******************************************************************************
 * Preprocessor directives.
 ******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARR_SIZE    (32)
#define MAX_INIT_VAL    (100)


/*******************************************************************************
 * Function prototypes.
 ******************************************************************************/
int find(int* pData, size_t len);


/*******************************************************************************
 * Function definitions.
 ******************************************************************************/
/*----------------------------------------------------------------------------*/
int main(void)
{
    // Init random seed.
    srand(time(NULL));

    // Populate test array.
    int rVal = rand() % ARR_SIZE;
    int arr[ARR_SIZE] = { 0 };
    int i = 0, count = rand() % MAX_INIT_VAL;

    for ( i = 0; i < ARR_SIZE; i++ )
    {
        if ( i == rVal )
        {
            count++;
            printf("Causing a hole at position %d.\n", i);
        }
        arr[i] = count + i;
    }
    for ( i = 0; i < ARR_SIZE; i++ )
    {
        printf("%3d ", arr[i]);
    }
    printf("\n\n");

    // Search for the hole.
    int iMissing = find(arr, ARR_SIZE);
    if ( iMissing == (-1) ) {
        printf("Could not find a hole.\n");
    } else {
        printf("Missing value detected: %d.\n", iMissing);
    }

    return 0;
}


/*----------------------------------------------------------------------------*/
int find(int* pData, size_t len)
{
    int i = 0;
    int left,middle,right;

    left = 0;
    right = len-1;
    middle = (left+right) / 2;

    /* Iterate until we converge. */
    while (left < right) {
        if ((pData[middle]-pData[left]) != (middle - left)) {
            /* An element is missing between the middle and left-
             * hand size extreme position.
             */
            if ((middle-left) == 1 && (pData[middle]-pData[left] > 1)) {
                return (pData[middle]-1);
            }   
            right = middle;
        } else if ((pData[right]-pData[middle]) != (right-middle)) {
            /* An element is missing between the middle and right-
             * hand size extreme position.
             */
            if ((right-middle) == 1 && (pData[right]-pData[middle] > 1)) {
                return (pData[middle]+1);
            }   
            left = middle;
        } else {
            return -1;
        }
        middle = (left+right) / 2;
    }   

    /* Couldn't find a break in data. Set is strictly monotonically
     * increasing with no holes.
     */
    return -1;
}