Search Insert Position Solution

Problem

Given a sorted array of distinct integers and a target value, find and return the target's index. If the target is not in the array, return the index where it would need to be inserted to keep the array sorted.

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 exists at index 2.

When the target is absent:

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 would be inserted between 1 and 3, so the answer is index 1.

Intuition

Because the array is sorted, we can eliminate half the remaining candidates each step — the classic binary search setup. The insight that makes this problem clean is that when the search loop ends, the left pointer is sitting exactly at the insertion point: every move either pushed left right past a too-small value or pulled right left past a too-large one, so when they cross, left is the smallest index where the value would be ≥ target.

Approach 1 — Linear Scan

Walk the array left to right and return the first index where the value is at least the target. This is easy to reason about but does not exploit the sorted order.

Iterate through nums with index tracking.
As soon as nums[index] >= target, return index.
If the loop finishes, the target is larger than every element — return len(nums).

1def searchInsert(self, nums: list[int], target: int) -> int:
2    for index, value in enumerate(nums):
3        if value >= target:
4            return index
5    return len(nums)  # target belongs after every element

Time: O(n) — may scan every element before finding the position.
Space: O(1) — no extra storage.

Approach 2 — Binary Search

Maintain an inclusive [left, right] window and halve it each step. When the window closes (left > right), left is the insertion point.

Initialize left = 0, right = len(nums) - 1.
While left <= right, compute mid = left + (right - left) // 2.
If nums[mid] == target, return mid immediately.
If nums[mid] < target, the answer is in the right half: left = mid + 1.
If nums[mid] > target, the answer is in the left half: right = mid - 1.
Return left — the loop invariant guarantees it is the insertion position.

1def searchInsert(self, nums: list[int], target: int) -> int:
2    left, right = 0, len(nums) - 1
3    while left <= right:
4        mid = left + (right - left) // 2
5        if nums[mid] == target:
6            return mid
7        elif nums[mid] < target:
8            left = mid + 1   # target must be in the right half
9        else:
10            right = mid - 1  # target must be in the left half
11    return left  # when left > right, left is the insertion point

Time: O(log n) — search space halves on every iteration.
Space: O(1) — only two index variables needed.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	Tiny inputs or as a baseline to verify binary search output
Binary Search	O(log n)	O(1)	Any sorted array — the intended solution for this problem

Common Mistakes

Returning left - 1 when not found — the loop ends with left at the correct insertion index; subtracting one shifts it to the wrong slot.
Integer overflow in the midpoint formula — (left + right) / 2 overflows when both indices are near INT_MAX in Java and C++; always use left + (right - left) / 2.
Using strict > instead of >= in the linear scan — nums[i] > target would skip the case where the target already exists in the array.
Forgetting the post-loop return len(nums) in the linear approach — when the target is larger than every element, the loop exits without returning, so the explicit return n is required.
Mixing bound conventions mid-function — for example, initializing right = len(nums) (exclusive) but writing nums[mid] > target → right = mid - 1 (inclusive update) mixes the two conventions and produces off-by-one errors; stay with inclusive bounds throughout.

Search Insert Position — Solution