440. Upper Bound in Sorted Array

Given a sorted array nums and an integer target, return the upper bound — the index of the first element that is strictly greater than target. If all elements are ≤ target, return nums.length.

Input: A sorted integer array nums and integer target.

Output: First index i where nums[i] > target, or n if none exists.

Examples

Input: [1,3,5,7,9], 5
Output: 3
Explanation: nums[3]=7 is the first element > 5.

Input: [1,3,5,7,9], 9
Output: 5
Explanation: 9 is the largest element; upper bound is n=5.

Input: [2,2,2,2], 2
Output: 4
Explanation: All elements equal 2; upper bound is n=4.

Constraints

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

Asked by