Find the Missing Element in Arithmetic Progression

Problem:
Find the missing number in an Arithmetic Progression. An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: exactly one number from the original series is missing from the set of numbers which have been given to you. The rest of the given series is the same as the original AP. Find the missing number.

Input:
The first line contains an Integer N, which is the number of terms which will be provided as input. This is followed by N consecutive Integers, with a space between each pair of integers. All of these are on one line, and they are in AP (other than the point where an integer is missing).

Output:
One Number which is the missing integer from the series.
Sample Input:
5
1 3 5 9 11
Sample Output:
7

Explanation:
You are provided with 5 integers. As you can can observe, they have been picked from a series, in which the starting term is 1 and the common difference is 2. The only aberration, i.e. the missing term (7), occurs between 5 and 9. This is the missing element which you need to find.

Solution:
A Simple Solution is to linearly traverse the array and find the missing number. Time complexity of this solution is O(n).

We can solve this problem in O(Logn) time using Binary Search. The idea is to go to the middle element. Check if the difference between middle and next to middle is equal to diff or not, if not then the missing element lies between mid and mid+1. If the middle element is equal to n/2th term in Arithmetic Series (Let n be the number of elements in input array), then missing element lies in right half. Else element lies in left half.

Implementation:

int findMissing(int arr[], int low, int high, int diff)
{
    
    if (high <= low)
        return INT_MAX;
 
    // Find index of middle element
    int mid = low + (high - low)/2;
 
    if (arr[mid+1] - arr[mid] != diff)
        return (arr[mid] + diff);
 
    // The element just before mid is missing
    if (mid > 0 && arr[mid] - arr[mid-1] != diff)
        return (arr[mid-1] + diff);
 
    if (arr[mid] == arr[0] + mid*diff)
        return findMissingUtil(arr, mid+1, high, diff);
 
    return findMissingUtil(arr, low, mid-1, diff);
}
 

int findMissingTerm(int arr[], int n)
{
    
    int diff = (arr[n-1] - arr[0])/n;
 
    return findMissing(arr, 0, n-1, diff);
}