Search Insert Position

The key idea

Find the leftmost position where target could be inserted to keep the array sorted. Binary search for the first index whose value is >= target: when found, that index is the answer whether target is present or not, which unifies the hit and miss cases.

Problem

Given a sorted array of distinct integers nums and a target value target, 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.

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

Examples

Input: nums = [1,3,5,6], target = 5 Output: 2

Input: nums = [1,3,5,6], target = 2 Output: 1

Input: nums = [1,3,5,6], target = 7 Output: 4

Complexity

Time: O(log n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →