433. Find the Only Missing Element in Sorted Array

Given a sorted array containing n distinct integers from the range [1, n+1] with exactly one number missing, return the missing number. Solve in O(log n).

Input: A sorted integer array nums with values from [1, n+1], one missing.

Output: The missing integer.

Examples

Input: [1,2,4,5,6]
Output: 3
Explanation: arr[2]=4 but expected 3. Binary search: mid=2,arr[2]=4≠3→missing is in left half.

Input: [2,3,4,5]
Output: 1
Explanation: First element should be 1 but is 2. Missing is 1.

Input: [1,2,3,4]
Output: 5
Explanation: All 1..4 present; missing is 5 (n+1).

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= n+1
• All distinct
• Sorted ascending

Asked by