Search Insert Position
Problem
Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
- 1 ≤ nums.length ≤ 10⁴
- −10⁴ ≤ nums[i] ≤ 10⁴
- nums contains distinct values sorted in ascending order
- −10⁴ ≤ target ≤ 10⁴
Example
nums = [1,3,5,6], target = 52The algorithm performs a binary search over the interval [0, 4). It first computes mid = 2. Since nums[2] = 5 which is greater than or equal to the target, the search narrows to the left half by setting right = mid. The process continues until left and right converge to index 2, which is the correct position of the target.
Approach
Straightforward Solution
A linear scan through the array to find the first element greater than or equal to the target would be O(n), which is inefficient for large arrays.
Core Observation
The problem reduces to finding the first index where nums[index] is greater than or equal to the target. This is the classic lower-bound search problem on a sorted array.
Path to Optimal
Recognizing the sorted nature of nums allows the use of binary search to find the target or its insertion point in O(log n) time. The key insight is to maintain a search window [left, right) and narrow it by comparing the middle element to the target, adjusting boundaries accordingly until left == right, which is the insertion index.
Optimal Approach
Implement a binary search with left initialized to 0 and right to len(nums). While left < right, compute mid = (left + right) // 2. If nums[mid] >= target, move right to mid to search the left half; else, move left to mid + 1 to search the right half. When the loop ends, left is the correct insertion index.
Time
O(log n)
Each iteration halves the search space by adjusting left or right pointers, resulting in logarithmic time relative to the array size.
Space
O(1)
Only a fixed number of variables (left, right, mid) are used, with no additional data structures, resulting in constant auxiliary space.
Pattern Spotlight
Modified Binary Search (Lower Bound Search)
When searching for the insertion position in a sorted array, use binary search to find the smallest index where the element is greater than or equal to the target by adjusting the search boundaries based on comparisons, ensuring O(log n) time.
Solution
| 1 | class Solution: |
| 2 | def searchInsert(self, nums: List[int], target: int) -> int: |
| 3 | |
| 4 | left = 0 |
| 5 | right = len(nums) |
| 6 | |
| 7 | while left < right: |
| 8 | |
| 9 | mid = (left + right) // 2 |
| 10 | |
| 11 | if nums[mid] >= target: |
| 12 | right = mid |
| 13 | else: |
| 14 | left = mid + 1 |
| 15 | |
| 16 | return left |
| 1 | import java.util.List; |
| 2 | |
| 3 | public class Solution { |
| 4 | public int searchInsert(List<Integer> nums, int target) { |
| 5 | int left = 0; |
| 6 | int right = nums.size(); |
| 7 | |
| 8 | while (left < right) { |
| 9 | int mid = (left + right) / 2; |
| 10 | if (nums.get(mid) >= target) { |
| 11 | right = mid; |
| 12 | } else { |
| 13 | left = mid + 1; |
| 14 | } |
| 15 | } |
| 16 | |
| 17 | return left; |
| 18 | } |
| 19 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | int searchInsert(vector<int>& nums, int target) { |
| 8 | int left = 0; |
| 9 | int right = nums.size(); |
| 10 | |
| 11 | while (left < right) { |
| 12 | int mid = (left + right) / 2; |
| 13 | if (nums[mid] >= target) { |
| 14 | right = mid; |
| 15 | } else { |
| 16 | left = mid + 1; |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | return left; |
| 21 | } |
| 22 | }; |
| 1 | var Solution = function() {}; |
| 2 | |
| 3 | Solution.prototype.searchInsert = function(nums, target) { |
| 4 | let left = 0; |
| 5 | let right = nums.length; |
| 6 | |
| 7 | while (left < right) { |
| 8 | let mid = Math.floor((left + right) / 2); |
| 9 | if (nums[mid] >= target) { |
| 10 | right = mid; |
| 11 | } else { |
| 12 | left = mid + 1; |
| 13 | } |
| 14 | } |
| 15 | |
| 16 | return left; |
| 17 | }; |
Step-by-Step Solution
Initialize Search Boundaries to Cover Entire Array
| 4 | left = 0 |
| 5 | right = len(nums) |
Objective
To set the initial search window covering the entire array for binary search.
Key Insight
Setting left to 0 and right to len(nums) defines a half-open interval [left, right) that includes all valid insertion positions, including the position after the last element. This setup allows the binary search to correctly handle cases where the target is greater than all elements.
Interview Quick-Check
Core Logic
Initializing right to len(nums) instead of len(nums) - 1 allows the search to consider insertion at the end of the array.
State & Boundaries
The search interval is half-open [left, right), which simplifies boundary conditions and loop termination.
Narrow Search Window Using Binary Search to Find Target or Insertion Point
| 7 | while left < right: |
| 9 | mid = (left + right) // 2 |
| 11 | if nums[mid] >= target: |
| 12 | right = mid |
| 13 | else: |
| 14 | left = mid + 1 |
Objective
To iteratively reduce the search space by comparing the middle element to the target and adjusting boundaries accordingly.
Key Insight
By comparing nums[mid] to the target, the algorithm decides whether to search the left half (if nums[mid] >= target) or the right half (if nums[mid] < target). This ensures that the search converges to the smallest index where nums[index] >= target, which is the target's position or the correct insertion point. The loop continues until left equals right, guaranteeing the exact insertion index.
Interview Quick-Check
Core Logic
The binary search loop maintains the invariant that the target's insertion index lies within [left, right), shrinking this interval each iteration.
State & Boundaries
The loop condition left < right ensures the search continues until the interval is empty, at which point left is the insertion index.
Common Pitfalls & Bugs
Using right = mid instead of right = mid - 1 avoids missing the correct insertion point and prevents infinite loops.
Return the Computed Insertion Index
| 16 | return left |
Objective
To output the final position where the target is or should be inserted.
Key Insight
After the binary search loop terminates, left equals right and points to the smallest index where nums[left] is greater than or equal to the target. Returning left provides the correct answer for both found and not found cases.
Interview Quick-Check
Core Logic
Returning left leverages the binary search invariant that left is the lower bound insertion index.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
return leftReturn the insertion index after the search completes.
Returning left provides the smallest index where the target fits, satisfying the problem's requirement for both found and not found cases.
if nums[mid] >= target:Check if the middle element is greater than or equal to the target.
This comparison determines whether the target lies to the left (including mid) or to the right of mid, guiding the boundary adjustment.
right = midMove the right pointer to mid so the search continues in the left half including mid.
When nums[mid] is greater than or equal to the target, the correct position could be mid itself. Moving right to mid keeps mid inside the search interval so the algorithm does not skip the potential answer while still shrinking the search space.
left = mid + 1Advance the left boundary to mid + 1 to continue searching the right half of the array.
Because nums[mid] is smaller than the target, mid cannot be the insertion index. Moving left to mid + 1 removes mid and all earlier elements from the search space while preserving the binary search invariant.
right = len(nums)Initialize right pointer to the length of the array.
Setting right to len(nums) creates a half-open interval [left, right) that includes the position after the last element, enabling correct insertion at the array's end.
mid = (left + right) // 2Calculate the middle index of the current search interval.
Computing mid as the floor of (left + right) / 2 divides the search space in half, enabling logarithmic time complexity.
left = 0Initialize left pointer to the start of the array.
Starting at index 0 ensures the search covers the entire array from the beginning, allowing the algorithm to find the target or insertion point anywhere.
while left < right:Continue looping while the search interval is not empty.
The condition left < right maintains the invariant that the target's insertion index lies within [left, right), ensuring the loop terminates when the exact position is found.
else:Handle the case where the middle element is smaller than the target.
If nums[mid] is smaller than the target, the insertion position cannot be mid or any index before it. The search must therefore continue strictly in the right half of the interval.
Test Your Understanding
Why does the algorithm return left at the end of the binary search loop?
Because left converges to the smallest index where nums[left] is greater than or equal to the target, representing either the target's position if found or the correct insertion point if not.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Search Insert Position from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Search Insert Position drill