469. Find Smallest Missing Positive in Sorted Array

Given a sorted array nums (may contain negatives, zeros, or duplicates), return the smallest positive integer that does not appear in the array. Solve in O(log n).

Input: A sorted integer array nums.

Output: Smallest missing positive integer (>= 1).

Examples

Input: [1,2,3,4,5]
Output: 6
Explanation: All of 1-5 present; smallest missing positive is 6.

Input: [-3,-2,-1,0,1,2,4]
Output: 3
Explanation: 1 and 2 present but 3 missing.

Input: [2,3,4,5,6]
Output: 1
Explanation: 1 is the smallest missing positive.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• Sorted ascending

Asked by