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 <= 104The key idea behind #35 Search Insert Position is to determine where a target value should appear in a sorted array. If the target exists, return its index. If it does not exist, return the position where it should be inserted to maintain sorted order.
A straightforward approach is to scan the array from left to right and return the first index where the element is greater than or equal to the target. While simple, this approach runs in O(n) time.
A more optimal strategy uses Binary Search. Because the array is sorted, you can repeatedly divide the search space in half using two pointers and compare the middle element with the target. If the target is not found, the final pointer position naturally indicates the correct insertion index. This reduces the search time significantly.
The binary search approach achieves O(log n) time complexity with O(1) extra space, making it the preferred method for large arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan | O(n) | O(1) |
| Binary Search | O(log n) | O(1) |
take U forward
The iterative binary search approach involves using two pointers, 'left' and 'right'. We continue dividing the array into halves until we locate the target or determine where it should be inserted. The algorithm compares the target with the middle element and appropriately adjusts the 'left' or 'right' pointer based on this comparison.
Time Complexity: O(log n)
Space Complexity: O(1) since no extra space is used.
1function searchInsert(nums, target) {
2 let left = 0;
3 let right = nums.length - 1;
4 while (
The JavaScript implementation uses binary search logic for determining the correct position of the target in the sorted array.
In this approach, the binary search is implemented recursively. The function calls itself with updated bounds until the target is found or until it determines the correct insertion index. This approach makes use of stack space due to recursion but is logically intuitive.
Time Complexity: O(log n)
Space Complexity: O(log n) due to recursion stack.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem frequently appear in technical interviews, including FAANG-style interviews. It tests understanding of binary search fundamentals, edge cases, and efficient searching in sorted arrays.
The problem primarily uses a sorted array. No additional complex data structures are required, as the logic relies on index manipulation and comparisons within the array.
The optimal approach is binary search because the array is already sorted. By repeatedly dividing the search space, you can determine either the exact index of the target or the correct insertion position in O(log n) time.
Binary search works well because the array is sorted. This property allows us to eliminate half of the remaining elements at every step, making the search for the target or insertion index much faster than a linear scan.
The Python implementation uses recursion within the binary search algorithm to determine the index or insert position.