35. Search Insert Position - Explanation
Description
You are 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,0,2,4,6,8], target = 5
Output: 4Example 2:
Input: nums = [-1,0,2,4,6,8], target = 10
Output: 6Constraints:
1 <= nums.length <= 10,000.-10,000 < nums[i], target < 10,000numscontains distinct values sorted in ascending order.
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Arrays - Understanding how to traverse and access elements by index
- Binary Search - Knowing how to efficiently search in a sorted array by repeatedly halving the search space
1. Linear Search
Intuition
We scan the array from left to right looking for the first element that is greater than or equal to the target. If we find such an element, that index is where the target either exists or should be inserted. If no element qualifies, the target belongs at the end.
Algorithm
- Iterate through each index
iin the array. - If
nums[i] >= target, returni. - If the loop completes without returning, return
n(the length of the array to insert at the end).
Time & Space Complexity
- Time complexity:
- Space complexity: extra space.
2. Binary Search - I
Intuition
Since the array is sorted, we can use binary search to find the target in logarithmic time. We track the potential insertion point as we search. Whenever we find an element greater than the target, we update our answer and continue searching left for a potentially smaller valid index.
Algorithm
- Initialize
res = n(default insertion point at the end) and pointersl = 0,r = n - 1. - While
l <= r:- Compute
mid = (l + r) / 2. - If
nums[mid] == target, returnmid. - If
nums[mid] > target, setres = midand search left withr = mid - 1. - Otherwise, search right with
l = mid + 1.
- Compute
- Return
res(final insertion position).
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
res = len(nums)
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[mid] > target:
res = mid
r = mid - 1
else:
l = mid + 1
return resTime & Space Complexity
- Time complexity:
- Space complexity: extra space.
3. Binary Search - II
Intuition
A cleaner observation: when binary search ends without finding the target, the left pointer l naturally lands on the correct insertion position. This happens because l always moves past elements smaller than the target, stopping exactly where the target should go.
Algorithm
- Initialize pointers
l = 0andr = n - 1. - While
l <= r:- Compute
mid = (l + r) / 2. - If
nums[mid] == target, returnmid. - If
nums[mid] > target, search left withr = mid - 1. - Otherwise, search right with
l = mid + 1.
- Compute
- Return
las the insertion index (wherelnaturally lands on the correct position).
Time & Space Complexity
- Time complexity:
- Space complexity: extra space.
4. Binary Search (Lower Bound)
Intuition
This is the classic lower bound algorithm. We find the smallest index where the element is greater than or equal to the target. By using l < r as the condition and setting r = m when nums[m] >= target, we converge on the lower bound without needing a separate result variable.
Algorithm
- Initialize pointers
l = 0andr = n(note:rstarts atn, notn - 1). - While
l < r:- Compute
m = l + (r - l) / 2. - If
nums[m] >= target, setr = m. - Otherwise, set
l = m + 1.
- Compute
- Return
l(the lower bound position).
Time & Space Complexity
- Time complexity:
- Space complexity:
5. Built-In Binary Search Function
Intuition
Most languages provide a built-in binary search or lower bound function. These functions return the index where the target is found or the position where it should be inserted to maintain sorted order. Using these avoids reimplementing binary search.
Algorithm
- Call the language's built-in binary search function (e.g.,
bisect_leftin Python,lower_boundin C++,Arrays.binarySearchin Java). - If the function returns a negative value (Java), convert it to the insertion point (
-index - 1). - Return the resulting index.
Time & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Off-by-One Errors in Binary Search Boundaries
A frequent mistake is using incorrect loop conditions or boundary updates. Using l < r instead of l <= r (or vice versa) without adjusting the logic accordingly can cause the algorithm to miss elements or enter infinite loops. Similarly, setting r = mid instead of r = mid - 1 in certain variants can lead to incorrect results or infinite loops.
Forgetting to Handle the "Insert at End" Case
When the target is larger than all elements in the array, the insertion position should be n (the length of the array). Beginners often forget to account for this case, either returning -1, causing an index out of bounds error, or returning the last index incorrectly. Always ensure your algorithm correctly returns n when the target exceeds all array elements.
Sign in to join the discussion