Search Insert Position
Easy · binary search
You are given a list nums of distinct integers sorted in ascending order, and an integer target.
If target is in the list, return its index. Otherwise return the index where it would have to be inserted so that the list stays sorted. That index can be 0 (before everything) or len(nums) (after everything).
Examples
Example 1
Input: nums = [2, 4, 7, 9], target = 7
Output: 2
7 is in the list, at index 2.
Example 2
Input: nums = [2, 4, 7, 9], target = 5
Output: 2
5 is not there. Putting it at index 2 gives [2, 4, 5, 7, 9], which is still sorted.
Example 3
Input: nums = [2, 4, 7, 9], target = 12
Output: 4
12 is larger than everything, so it goes at the very end, index 4.
Constraints
- 1 <= len(nums) <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in strictly ascending order.
- -10^4 <= target <= 10^4