Watch 10 video solutions for Search Insert Position, a easy level problem involving Array, Binary Search. This walkthrough by take U forward has 443,441 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 it does not exist, return the index where it should be inserted to keep the array sorted.
Approach 1: Linear Scan (O(n) time, O(1) space)
Walk through the array from left to right and compare each element with the target. The first element greater than or equal to the target gives the correct insertion index. If you reach the end without finding such an element, the target belongs at index n. This works because the array is already sorted. The downside is the O(n) time complexity, which becomes inefficient for large inputs.
Approach 2: Iterative Binary Search (O(log n) time, O(1) space)
The sorted property allows you to use binary search. Maintain two pointers left and right. Compute mid and compare nums[mid] with the target. If equal, return mid. If the target is smaller, move the right boundary. If larger, move the left boundary. When the loop ends, left represents the exact insertion position. This works because binary search narrows the valid region where the target could appear while preserving sorted order in the array.
Approach 3: Recursive Binary Search (O(log n) time, O(log n) space)
The same binary search logic can be implemented recursively. Each recursive call processes half of the remaining range. The base case occurs when the search boundaries cross; at that point the left pointer indicates where the target should be inserted. This version is often easier to reason about conceptually, but recursion introduces O(log n) stack space due to the call stack.
Recommended for interviews: Iterative binary search. Interviewers expect you to recognize that the input is sorted and immediately apply binary search for O(log n) time. Starting with the linear scan demonstrates baseline reasoning, but implementing binary search correctly shows strong algorithm fundamentals and familiarity with classic search patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple baseline solution or very small arrays |
| Iterative Binary Search | O(log n) | O(1) | Best choice when the array is sorted and large |
| Recursive Binary Search | O(log n) | O(log n) | When recursion is preferred for clarity or teaching binary search |