Search Insert Position
Description
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity.
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 is not found. It 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 not found. It is greater than all elements, so it would be inserted at the end (index 4).
Example 4:
Input: nums = [1, 3, 5, 6], target = 0
Output: 0
Explanation: 0 is not found. It is smaller than all elements, so it would be inserted at the beginning (index 0).
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums contains distinct values sorted in ascending order-10^4 <= target <= 10^4
Complexity
Show Complexity
- Time:
O(log n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Binary search to find position
- Approach
- Use binary search. If target found, return index. If not found, left pointer will be at the insert position.
- Complexity
- Standard binary search with O(log n) time
Solutions
Show PY Solution
def solution(nums: list[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = right - (right - left) // 2
v = nums[mid]
if v == target:
return mid
if v < target:
left = mid + 1
else:
right = mid - 1
return left