385. Where It Would Go
A conveyor belt carries parcels in increasing order of weight, and no two parcels weigh the same. A new parcel of weight target has to be placed on the belt without breaking the sorted order.
Given the sorted array nums of weights already on the belt, return the index at which a parcel of weight target sits, if one is already there, or the index where it would have to be inserted to keep the belt sorted. The answer is a value from 0 to nums.length. Your solution should run in O(log n) time.
Example 1
- Input:
- nums = [10,20,30,40], target = 25
- Output:
- 2
- Explanation:
A parcel of weight 25 belongs between 20 and 30, so it goes at index 2.
Example 2
- Input:
- nums = [10,20,30,40], target = 40
- Output:
- 3
- Explanation:
A parcel of weight 40 is already at index 3.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i], target ≤ 109nums is strictly increasing.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)