Search Insert Position
Given a sorted array of distinct integers nums and an integer target, return the index if target is found.
If target is not found, return the index where it would be inserted in order to maintain the sorted order of nums.
Your solution must run in O(log n) time.
Example 1
Input
nums = [1,3,5,6], target = 5Output
2The target value 5 is found at index 2.
Example 2
Input
nums = [1,3,5,6], target = 2Output
1The target value 2 is not found, and it should be inserted at index 1 to keep the array sorted.
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