Last Updated on March 30, 2022 by Ria Pathak

### CONCEPTS USED:

Binary Search

### DIFFICULTY LEVEL:

Medium

### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given an array

`A`

, such that it is arranged in an`Arithmetic Progression`

, but one element from this A.P. is missing, find it.

**See original problem statement here**

#### For Example:

```
Input : A = [3, 6, 12, 15, 18]
Output : 9
Explanation : In the given A.P. series starting with initial element 3 and Common Difference 3, 9 is the element that is missing between 6 and 12.
```

*Can we use Binary Search here ?*

Given that the array forms an A.P. this implies that it is either sorted in ascending or descending order and we need to search a missing number in it.

`Binary Search`

would be an efficient alternative here.

### OBSERVATION:

Every element in an A.P. can be calculated using its position i.e.

`arr[i] = arr[0] + i*diff`

### SOLVING APPROACH:

*First check for corner cases :*

First check whether the missing element lies near one of the corner points by taking out difference of first and second elements and difference of last and second last elements and comparing these differences with each other. If they are not equal, this implies that the missing number lies near corner points and we can easily compute the missing number.

Else we will follow below approach –

The idea is to use

`Binary Search`

.We initialize

`low`

and`high`

as`0`

and`n-1`

, and calculate`mid`

as

`mid = low + (high - low)/2`

If the element present at

`mid`

matches the calculated value at`mid`

, this implies that elements at the lower half are all positioned correctly, so we search in the right half.else we store the calculated value and search in the lower half till

`low 6. In this way, we will have the last value that was not at its right position stored with us which will be our`

result`.

### SOLUTIONS:

#include <stdio.h> #include <stdio.h> int MissingAP(int *arr, int low, int high, int diff, int missing_ele){ if(low <= high){ int mid = low + (high - low)/2; /* if curr element is at its right place in AP we will search in the lower half then */ if(arr[mid] == arr[0] + mid*diff) return MissingAP(arr, mid+1, high, diff, missing_ele); /* else save the value that should be here and further search in the lower half */ else{ missing_ele = arr[0] + mid*diff; return MissingAP(arr, low, mid - 1, diff, missing_ele); } } //finally return the ele that was not found on its place return missing_ele; } int main() { int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); int arr[n]; for(int i=0; i<n; i++) scanf("%d", &arr[i]); //check if missing element lies at one of the ends or close to one of the ends int left_diff = arr[1] - arr[0]; int right_diff = arr[n-1] - arr[n-2]; int diff, missing_ele; //if left == right, missing element lies inside of the array if(left_diff == right_diff){ diff = left_diff; //we will go on checking inside the array printf("%d\n", MissingAP(arr, 0, n-1, diff, -1)); continue; } //else missing ele is at one of the corners or near corner if(left_diff < right_diff){ missing_ele = arr[n-1] - left_diff; printf("%d\n", missing_ele); } else{ missing_ele = arr[0] + right_diff; printf("%d\n", missing_ele); } } return 0; }

#include <bits/stdc++.h> using namespace std; int MissingAP(int *arr, int low, int high, int diff, int missing_ele){ if(low <= high){ int mid = low + (high - low)/2; /* if curr element is at its right place in AP we will search in the lower half then */ if(arr[mid] == arr[0] + mid*diff) return MissingAP(arr, mid+1, high, diff, missing_ele); /* else save the value that should be here and further search in the lower half */ else{ missing_ele = arr[0] + mid*diff; return MissingAP(arr, low, mid - 1, diff, missing_ele); } } //finally return the ele that was not found on its place return missing_ele; } int main() { int t; cin>>t; while(t--){ int n; cin>>n; int arr[n]; for(int i=0; i<n; i++) cin>>arr[i]; //check if missing element lies at one of the ends or close to one of the ends int left_diff = arr[1] - arr[0]; int right_diff = arr[n-1] - arr[n-2]; int diff, missing_ele; //if left == right, missing element lies inside of the array if(left_diff == right_diff){ diff = left_diff; //we will go on checking inside the array cout<<MissingAP(arr, 0, n-1, diff, -1)<<"\n"; continue; } //else missing ele is at one of the corners or near corner if(left_diff < right_diff){ missing_ele = arr[n-1] - left_diff; cout<<missing_ele<<"\n"; } else{ missing_ele = arr[0] + right_diff; cout<<missing_ele<<"\n"; } } return 0; }

import java.util.*; import java.io.*; public class Main { static int MissingAP(int []arr, int low, int high, int diff, int missing_ele){ if(low <= high){ int mid = low + (high - low)/2; /* if curr element is at its right place in AP we will search in the lower half then */ if(arr[mid] == (arr[0] + mid*diff)) return MissingAP(arr, mid+1, high, diff, missing_ele); /* else save the value that should be here and further search in the lower half */ else{ missing_ele = arr[0] + mid*diff; return MissingAP(arr, low, mid - 1, diff, missing_ele); } } //finally return the ele that was not found on its place return missing_ele; } public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t != 0){ int n = sc.nextInt(); int arr[] = new int[n]; for(int i=0; i<n; i++) arr[i] = sc.nextInt(); //check if missing element lies at one of the ends or close to one of the ends int left_diff = arr[1] - arr[0]; int right_diff = arr[n-1] - arr[n-2]; int diff, missing_ele; //if left == right, missing element lies inside of the array if(left_diff == right_diff){ diff = left_diff; //we will go on checking inside the array System.out.println(MissingAP(arr, 0, n-1, diff, -1)); t--; continue; } //else missing ele is at one of the corners or near corner if(left_diff < right_diff){ missing_ele = arr[n-1] - left_diff; System.out.println(missing_ele); } else{ missing_ele = arr[0] + right_diff; System.out.println(missing_ele); } t--; } } }

[forminator_quiz id="1534"]

**Space Complexity**: O(1)

This article tried to discuss the concept of **Binary Search**. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.