439. Lower Bound in Sorted Array

Given a sorted array nums and an integer target, return the lower bound — the index of the first element that is greater than or equal to target. If all elements are less than target, return nums.length.

Input: A sorted integer array nums and integer target.

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

Examples

Input: [1,3,5,7,9], 5
Output: 2
Explanation: nums[2]=5>=5; first such index is 2.

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

Input: [1,3,5,7,9], 10
Output: 5
Explanation: No element >=10; return n=5.

Constraints

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

Asked by