Lesson

6.8Find Missing Element

Problem Statement:
Given a sorted array representing an arithmetic progression (AP), one element is missing. Write a function to find the missing element using binary search.

Sample Example:

Input: arr = [1, 3, 5, 7, 11]

Output: 9

Explanation: The missing element in the arithmetic progression is 9, which is the expected value between 7 and 11 based on the common difference of 2.

Approaches

Brute Force Approach

Idea:
- Calculate the expected difference d in the progression. Then, iterate through the array and find the position where the difference between consecutive elements is not equal to d. The missing number is found at this position.
Steps:
1. Calculate the common difference d.
2. Iterate through the array to find the first occurrence where the difference between consecutive elements is not equal to d.
3. Return the missing number based on this mismatch.
Time Complexity: O(n)
Space Complexity: O(1)
Example Code:

Dry Run:
- Input: arr = [1, 3, 5, 7, 11]
- Expected difference: d = 2
- Iterate over the array:
  - At index 3, arr[3] = 7 and arr[4] = 11, so arr[4] - arr[3] = 4, which is not equal to d.
- Missing element: 7 + 2 = 9.
Efficient Approach (Binary Search)
Idea:
- Use binary search to find the missing element. Since the array is sorted and forms an arithmetic progression, the missing element must lie where the progression deviates from the expected values.
Steps:
1. Set two pointers low = 0 and high = n-1.
2. Calculate the common difference d.
3. Use binary search to find the missing element by checking whether the middle element is in its correct position relative to the common difference.
4. Adjust the low and high pointers based on whether the missing element lies in the left or right half.
Time Complexity: O(log n)
Space Complexity: O(1)
Example Code:

Dry Run:
- Input: arr = [1, 3, 5, 7, 11]
- Expected difference: d = 2
- Perform binary search:
  - Middle index: 2, element at arr[2] = 5 is in the correct position.
  - Adjust low = 3.
  - Middle index: 3, element at arr[3] = 7 is in the correct position.
  - Adjust low = 4.
- Missing element: 1 + 4 * 2 = 9.

Example Test Case

Complexity Analysis

Brute Force Approach

Time Complexity: O(n)
Space Complexity: O(1)

Binary Search Approach

Time Complexity: O(log n)
Space Complexity: O(1)

Conclusion

The binary search approach is more efficient for large arrays, reducing the time complexity from O(n) to O(log n).

Previous Next