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.
1#include <stdio.h>
2
3int searchInsert(int* nums, int numsSize, int target) {
4 int left = 0, right = numsSize - 1;
5 while (left <= right) {
6 int mid = left + (right - left) / 2;
7 if (nums[mid] == target) return mid;
8 else if (nums[mid] < target) left = mid + 1;
9 else right = mid - 1;
10 }
11 return left;
12}
13
14int main() {
15 int nums[] = {1, 3, 5, 6};
16 int target = 5;
17 int result = searchInsert(nums, 4, target);
18 printf("%d\n", result);
19 return 0;
20}
21This solution uses a binary search to find the target. If the target is found, it returns the index. If not, it returns the position where the target should be inserted to maintain sorted order.
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#include
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.
This C solution uses recursion to implement binary search to find the index or the prospective insertion position of the target.