Problem statement

Given a sorted array of distinct integers and a target, return the index of target if found; otherwise return the index where it would be inserted to keep the order.

Must run in O(log n).

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= nums.length <= 30
• -100 <= nums[i], target <= 100
• Distinct sorted values.

Hints for Search Insert Position

1. Hint 1

   This is lower_bound: the first index whose value is >= target.

2. Hint 2

   Use half-open bounds [lo, hi) and shrink until they meet.

How to solve Search Insert Position

Both cases the problem asks about — "where is it" and "where would it go" — are the same query: the first index whose value is at least the target, the classic lower_bound. If the value there equals the target you found it; if not, that is exactly the insertion point. One search, no special-casing.

Approach

1. Search a half-open range [lo, hi) with hi = n, so n itself is a legal answer (insert at the end).
2. While lo < hi, take mid = lo + (hi - lo) / 2.
3. If nums[mid] < target, then mid and everything left is too small — set lo = mid + 1.
4. Otherwise mid is still a candidate — set hi = mid, keeping it in range.
5. When the range is empty, lo is the answer.

Why it works

The invariant is that the answer always lies in [lo, hi]: everything below lo is strictly less than the target and everything at or above hi is at least the target. Both branches preserve it while strictly shrinking the range, so lo converges on the boundary between the two. Because the array is sorted and distinct, that boundary is precisely the target's index if present and its insertion point otherwise.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Use a half-open upper bound of n, not n - 1 — the target may belong after the last element.
• With half-open bounds, hi = mid (not mid - 1), because mid may itself be the answer. The lo = mid + 1 branch is what guarantees progress.
• The loop condition is lo < hi here, unlike the inclusive-range variant.

Reference solution

Python

from typing import List

def searchInsert(nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Java

public static int searchInsert(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

C++

int searchInsert(vector<int>& nums, int target) {
    int lo = 0, hi = (int) nums.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

JavaScript

var searchInsert = function(nums, target) {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy