# Finding “holes” in a sorted list of numbers

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;
}```