Find the Insertion Index

You are given an array nums sorted in ascending order (with distinct integers) and an integer target. Return the index at which target would be inserted into nums so that the array remains sorted. If target already exists in nums, return its index.

Your solution should run in O(log n) time.

Example 1

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 is found at index 2.

Example 2

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 would be inserted between 1 and 3, at index 1.

Example 3

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: 7 is larger than every element, so it is inserted at
the end.

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values, sorted in ascending order.
• -10^4 <= target <= 10^4