Search Insert Position

Problem in Plain English

You are given a sorted array of distinct integers and a target value. Return the index of the target when present, or the index where it belongs in sorted order when absent.

Problem Statement

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found.

If the target is absent, return the index where it would be inserted in order. The required solution runs in $O(log n)$ time.

Constraints

$1 \leq n \leq 10^4$ , where n is nums.length.
$-10^4 \leq nums[i] \leq 10^4$ .
nums contains distinct values sorted in ascending order.
$-10^4 \leq target \leq 10^4$ .

Examples

Example 1

Input: nums = [1, 3, 5, 6], target = 2
Output: 1

The value 2 is absent and belongs between 1 and 3, so the answer is 1.

Example 2

Input: nums = [1, 3, 5, 6], target = 5
Output: 2

The value 5 is found at index 2, so the answer is 2.

Example 3

Input: nums = [1, 3, 5, 6], target = 7
Output: 4

The value 7 is absent and belongs after every element, so the answer is 4.

Example 4

Input: nums = [5], target = 2
Output: 0

The only value is greater than 2, so insert before it at index 0. There is no empty-array case under the constraints.

Intuition

The insertion index is the number of array values smaller than the target. This also gives the existing index when the target is present, because the array is sorted and distinct. In Example 1, only 1 is smaller than 2, so index 1 separates values below 2 from values above it. Binary search locates that separation by ruling out half the remaining positions after each comparison.

Approaches

Linear Scan

Solution Details

Reveal Linear Scan: intuition, complexity, and code

Intuition

Scan from the smallest value until the first value at least as large as the target. All preceding values must stay before the target, so that index is either its existing position or its insertion slot. This baseline uses sorted order to stop early but does not meet the required logarithmic runtime.

Step-by-Step Logic

Inspect indices from left to right until a value is at least target. Example 1 starts at i = 0 with value 1 and target 2.
When the value is smaller, continue to the next index; 1 is smaller than 2, so advance to i = 1.
Return the first qualifying index immediately. At i = 1, value 3 is greater than 2, so return 1; an equal value would use the same branch.
If every value is smaller, return nums.length to represent insertion after the final element.

Why It Works

Before each index i, every inspected value is strictly smaller than target. If nums[i] is at least target, sorted order makes all later values at least target as well, so exactly i values precede the target. If no position qualifies, all n values are smaller and insertion belongs at n. An equality therefore returns the existing position without a special branch.

Dry Run

Linear Scan: variable states at each step
`i`	`nums[i]`	`nums[i] >= 2`	action
`0`	`1`	no	continue
`1`	`3`	yes	return `1`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Let n be nums.length. A target greater than the final value forces exactly n comparisons, giving worst-case O(n) time. An early answer can take constant time. The loop stores one index and returns one integer, so auxiliary space is O(1); the array is neither copied nor modified. This baseline fails the required O(log n) runtime.

Code

Solution.java

1class Solution {2    public int searchInsert(int[] nums, int target) {3        for (int i = 0; i < nums.length; i++) {4            if (nums[i] >= target) {5                return i;6            }7        }8        return nums.length;9    }10}

Hints

Hint 1

A sorted input with a logarithmic time requirement points directly at binary search rather than a scan.

Hint 2

Trace where left and right finish when the target is missing: left always stops at the first larger element.

Hint 3

Return left after the loop instead of -1, since an exact hit already returns from inside the loop.

Edge Cases

A target below every element, such as 0 in [1, 3, 5, 6], returns 0.
A target above every element, such as 7 in [1, 3, 5, 6], returns nums.length.
A single-element array returns 0 when the target fits before it and 1 when it fits after it.

Common Mistakes and Interview Tips

Returning right or mid instead of left after the loop, which points one slot too early.
Looping while left < right instead of left <= right, which skips the final single-element check.
Computing mid as (left + right) / 2 in a fixed-width language without the overflow-safe form left + (right - left) / 2.

Key Takeaway

A standard binary search already finds insertion points: when the loop ends, left is the lower bound where a missing value belongs.