Watch 10 video solutions for Search Insert Position, a easy level problem involving Array, Binary Search. This walkthrough by NeetCode has 89,929 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums contains distinct values sorted in ascending order.-104 <= target <= 104Problem Overview: You are given a sorted array of distinct integers and a target value. Return the index if the target exists. If not, return the index where it should be inserted to maintain sorted order.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest idea is to iterate through the array from left to right and stop when you find the first element greater than or equal to the target. That index is either the position of the target or the correct insertion point. If the loop finishes without finding such an element, the target should be inserted at the end of the array. This approach is straightforward but inefficient for large inputs because it may require scanning the entire array.
Approach 2: Iterative Binary Search (O(log n) time, O(1) space)
The array is already sorted, which makes binary search the natural choice. Maintain two pointers left and right representing the current search range. Compute the middle index and compare nums[mid] with the target. If they match, return mid. If the target is larger, move left to mid + 1; otherwise move right to mid - 1. When the loop finishes, left will be the correct insertion position because it points to the first element greater than the target.
Approach 3: Recursive Binary Search (O(log n) time, O(log n) space)
This method applies the same binary search logic but expresses it through recursion. Each recursive call reduces the search range by half based on the comparison with the middle element. When the search interval becomes invalid (left > right), the correct insertion index is simply left. The algorithm still performs logarithmic comparisons, but recursion adds call stack overhead, giving it O(log n) auxiliary space.
Recommended for interviews: Interviewers expect the binary search solution because the array is sorted. Showing the linear scan first demonstrates baseline reasoning, but implementing the iterative binary search proves you recognize the sorted array → logarithmic search optimization. The iterative version is usually preferred over recursion since it avoids extra stack usage while keeping the same O(log n) performance.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Quick baseline solution or when the array size is very small |
| Iterative Binary Search | O(log n) | O(1) | Best choice when the array is sorted and you need optimal performance |
| Recursive Binary Search | O(log n) | O(log n) | Useful for learning recursion or when implementing divide-and-conquer patterns |