Search Insert Position
Task example: Search Insert Position
Given distinct integers in increasing order and a target, return its index if present. Otherwise, return the index where it belongs in sorted order. Do not insert anything or change nums. The required runtime is O(log n); the linear scan is a baseline for comparison.
Indices start at zero. For target 2, return 1; for target 5, return 2; for target 7, return 4. The answer may equal len(nums), meaning after the last value.
Linear scan: video explanation
nums = [1, 3, 5, 6], target = 2 → 1
Prefer reading? Follow the steps below.
- Scan from left to right. Stop at the first nums[i] >= target: equality means the target exists; a greater value means target belongs just before it.
- For target 2 in [1, 3, 5, 6], skip 1 and stop at 3. Return index 1 without changing the array.
- If the loop finishes, every value is smaller. Return len(nums), the insertion position after the last element. This return belongs outside the loop.
Time complexity · O(n)
In the worst case, the scan checks all n values. A match at the first index takes O(1) time.
Space complexity · O(1)
Only the loop index is stored. No extra array or recursion is used.
Binary search: video explanation
nums = [1, 3, 5, 6], target = 2 → 1
Prefer reading? Follow the steps below.
- Set left = 0 and right = len(nums) - 1. While left <= right, check the middle candidate.
- If nums[mid] == target, return mid. If it is smaller, move left to mid + 1; otherwise, move right to mid - 1.
- For target 2, first check 3 at index 1 and move right to 0. Then check 1 at index 0 and move left to 1. Now left > right.
- Return left, not -1. All discarded values before left are smaller than target; all discarded values after right are larger. When the range is empty, left marks the correct insertion boundary.
Unlike the O(n) baseline, binary search meets the required O(log n) runtime by discarding roughly half of the candidates each step. Both approaches use O(1) extra space.
Time complexity · O(log n)
Each unsuccessful comparison roughly halves the remaining range. At most O(log n) iterations are needed; an immediate middle match is O(1).
Space complexity · O(1)
This iterative solution stores left, right, and mid. It creates no subarrays and uses no recursive call stack.