Search Insert Position
Problem Description
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 = 7Output: 4
Constraints:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
numscontains distinct values sorted in ascending order.- -104 <= target <= 104
Solve it on LeetCode
Approaches
1. Linear Search
Intuition:
A straightforward approach to solve this problem is to go through the array and find the target or the position where it can be inserted in order. This is done by iterating over the array and checking each element against the target.
Steps:
- Iterate through each element in the array.
- If the current element is equal to the target, return its index.
- If the current element is greater than the target, return the current index since that is where the target should be inserted.
- If the loop completes without finding a position, it means the target is larger than all elements, so return the length of the array as the insertion point.
Code:
- Time Complexity: O(n), where n is the number of elements in the array. This is because we may have to check each element in the worst case.
- Space Complexity: O(1), as there is no extra space required for this approach.
2. Binary Search
Intuition:
Since the array is sorted, we can use binary search to find the position for the target more efficiently. Binary search involves dividing the problem space in half during each iteration, making it much faster than a linear search.
Steps:
- Initialize two pointers:
leftat the start andrightat the end of the array. - While
leftis less than or equal toright: - Calculate
midas the average ofleftandright(careful for overflows by usingleft + (right - left) / 2). - If
nums[mid]is equal to the target, returnmid. - If
nums[mid]is less than the target, movelefttomid + 1. - If
nums[mid]is greater than the target, moverighttomid - 1. - If we didn't find the target,
leftwill be the position where the target should be inserted.
Code:
- Time Complexity: O(log n), where n is the number of elements in the array. Binary search reduces the problem size by half each iteration, leading to a logarithmic time complexity.
- Space Complexity: O(1), as binary search uses a constant amount of extra space.