Search Insert Position
Understanding the Problem
We have a sorted array of unique integers and a target value. If the target already exists in the array, return its index. If it doesn't, return the index where it would need to go to keep the array sorted.
The question reduces to: what is the leftmost position where target could be placed without breaking the sorted order? If target matches an element, that element's index is the answer. If it doesn't, the answer is the index of the first element greater than target, or the array length if target is larger than everything.
This is the "lower bound" problem from binary search: find the first index i where nums[i] >= target. That single framing handles both the "found" and "not found" cases.
Key Constraints:
1 <= nums.length <= 10^4→ The array has at most 10,000 elements. An O(n) scan would be fast enough in practice, but the problem explicitly requires O(log n).numscontains distinct values sorted in ascending order → Sorted + distinct is a strong signal for binary search. No duplicates means there's exactly one correct insert position.-10^4 <= target <= 10^4→ The target could be smaller than all elements (insert at index 0) or larger than all elements (insert at end). Both edge cases matter.
Approach 1: Linear Scan
Intuition
Walk through the array from left to right and find the first element that is greater than or equal to the target. If we find such an element, its index is the insert position. If we reach the end without finding one, the target belongs at the end.
This is correct but does not meet the O(log n) requirement. It does define the target the binary search will optimize: the linear scan checks every element one by one, while binary search performs the same logical task and discards half the remaining range at each step.
Algorithm
- Iterate through the array with index
ifrom 0 to n - 1. - If
nums[i] >= target, returni. This is either the target itself or the first element larger than it. - If the loop finishes without returning, return
n. The target is larger than every element.
Example Walkthrough
Code
- Time Complexity: O(n). In the worst case (target is larger than all elements), we scan the entire array.
- Space Complexity: O(1). Only uses a single loop variable. No extra data structures.
The linear scan works but doesn't meet the O(log n) requirement. Since the array is sorted, we can use binary search to eliminate half the search range at each step.
Approach 2: Binary Search
Intuition
The array is sorted, which is what makes O(log n) possible. Binary search finds an element in a sorted array by discarding half the range at each step.
The task is not an exact-match search. We need the correct insert position, which is the first index where nums[i] >= target. This is the "lower bound", and it handles both cases:
- If the target exists, the lower bound is the target's index.
- If the target doesn't exist, the lower bound is where it would be inserted.
The standard binary search template for lower bound works like this: maintain a search window [left, right). At each step, check the middle element. If it's less than the target, the answer must be in the right half, so move left to mid + 1. If it's greater than or equal to the target, the answer could be mid itself or something to the left, so move right to mid. When the window collapses (left == right), left is the answer.
The loop maintains an invariant: the answer always lies in the half-open range [left, right). When nums[mid] < target, every index from left to mid holds a value smaller than target, so none of them can be the lower bound, and left moves to mid + 1. When nums[mid] >= target, mid itself is a candidate and everything to its right is also >= target, so right moves to mid to keep mid in range while discarding the rest.
Each iteration strictly shrinks the range, so the loop terminates when left == right. At that point left is the smallest index where nums[i] >= target. If no such index exists (target exceeds every element), left equals nums.length, which is where the target would be inserted.
Algorithm
- Set
left = 0andright = nums.length. - While
left < right: - Compute
mid = left + (right - left) / 2to avoid integer overflow. - If
nums[mid] < target, setleft = mid + 1. - Otherwise, set
right = mid. - Return
left.
Example Walkthrough
Code
- Time Complexity: O(log n). Each iteration halves the search range. Starting with n elements, we need at most log2(n) iterations.
- Space Complexity: O(1). Only uses a few integer variables. No recursion, no extra data structures.