Lower Bound Index

You are given an integer array nums of distinct values sorted in ascending order, and an integer target.

Return the first index whose value is greater than or equal to target. If every value in nums is smaller than target, return nums.length.

Equivalently: return the index target occupies if it is present, and otherwise the index it would occupy if it were inserted while keeping the array sorted.

You must write an algorithm with $O(\log n)$ runtime complexity.

Examples

Example 1

Input: nums = [1,3,5,6], target = 5
Output: 2
Explanation: 5 is present at index 2, and it is the first value at least 5.

Example 2

Input: nums = [1,3,5,6], target = 2
Output: 1
Explanation: 2 is absent. The first value at least 2 is the 3 at index 1, which is also where 2 would be inserted.

Example 3

Input: nums = [1,3,5,6], target = 7
Output: 4
Explanation: Every value is smaller than 7, so the answer is nums.length, one past the last index.