Search Insert Position
Easy · Binary Search · Array · Binary Search
Problem
You are given an array nums of distinct integers sorted in ascending order, and an integer target.
If target is in nums, return its index. Otherwise, return the index where target would be inserted so that nums stays sorted. That index can be len(nums).
Your algorithm must run in O(log n) time.
Examples
Input: nums = [2,4,7,11], target = 7 Output: 2
7 is already present at index 2.
Input: nums = [2,4,7,11], target = 9 Output: 3
9 belongs between 7 and 11, so it would be placed at index 3.
Input: nums = [2,4,7,11], target = 1 Output: 0
1 is smaller than every value, so it goes at the front.
Constraints
- 1 <= len(nums) <= 10^4
- -10^4 <= nums[i], target <= 10^4
- nums holds distinct values sorted in ascending order
Approaches
- Linear scan for the first value not smaller — time O(n), space O(1)
Follow-up
What if values may repeat? Returning the first index whose value is at least target still works and gives the leftmost copy (a lower bound). To insert after every copy, change < to <= (an upper bound); the difference between the two is the number of copies.
Related problems
Start free on Cariara · Coding problems · System design studio
