Search Insert Position

EasyModified Binary SearchJuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given an array nums of distinct integers sorted in ascending order, and an integer target. If target is in nums, return its index. If it isn't, return the index where it would be inserted to keep nums sorted, which can be anywhere from 0 to nums.length. Your solution must run in O(log n) time.

Examples

nums = [1,3,5,6], target = 5 returns 2

5 is already in the array, at index 2.

nums = [1,3,5,6], target = 2 returns 1

3 is the first value at least 2.

2 is missing. It belongs between 1 and 3, so it would go at index 1.

nums = [1,3,5,6], target = 7 returns 4

7 is larger than every value, so it would go at the end, index 4, which equals the array's length.

Constraints

1 <= nums.length <= 10^4
-10^4 <= nums[i], target <= 10^4
nums contains distinct values sorted in ascending order.

Hints

Hint 1

Whether or not target is present, what property does the answer's position have in terms of the values around it?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Both cases ask for the same index: the first position whose value is at least target. Binary search for it over the half-open range lo = 0, hi = n. If nums[mid] < target, the answer is to the right of mid, so lo = mid + 1; otherwise mid itself could be the answer, so hi = mid. When lo meets hi, it is the answer. Starting hi at n lets the search return the end position.

Time

O(log n)

Space

O(1)

Pitfall

Starting hi at n - 1 means the search can never return n, so a target larger than every value, like 7 in [1,3,5,6], gets 3 instead of 4. A standard search that returns -1 on a miss also answers the wrong question.

Solutions

class Solution {
    public 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;
    }
}

class Solution:
    def searchInsert(self, nums, 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