Search Insert Position

Easy Binary Search Bisect Original on LeetCode

Search Insert Position is a easy binary search problem solved with the bisect pattern. The best approach, optimal (bisect_left), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from linear scan up.

Problem

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

Examples

Example 1

Input: nums = [2, 4, 7, 9], target = 7
Output: 2

Example 2

Input: nums = [2, 4, 7, 9], target = 5
Output: 2
Why: 5 would go between 4 and 7.

Example 3

Input: nums = [2, 4, 7, 9], target = 10
Output: 4

Constraints

1 <= nums.length <= 10^4, sorted and distinct.
O(log n).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Linear scan	`O(n)`	`O(1)`
Optimal (bisect_left)	`O(log n)`	`O(1)`

1Linear scan

TimeO(n)

SpaceO(1)

Return the first index whose value is at least target.

Walk forward until nums[i] >= target.

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0;
        while (i < nums.length && nums[i] < target) i++;
        return i;
    }
}

2Optimal (bisect_left)

TimeO(log n)

SpaceO(1)

Binary search for the first index where nums[i] >= target over [0, n).

lo = 0, hi = n; standard bisect_left loop.

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] >= target) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
}

Edge cases to test

Target before the first element (0)
Target after the last element (n)

Hints

Hint 1

This is exactly bisect_left.

FAQ

What is the best time complexity for Search Insert Position?

Optimal (bisect_left) runs in O(log n) time and O(1) extra space.

Which pattern does Search Insert Position use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Floor in a Sorted Array, Ceil in a Sorted Array.

Is there a brute force solution for Search Insert Position?

Yes. Linear scan takes O(n) time and O(1) space. Return the first index whose value is at least target.

Which edge cases should I test for Search Insert Position?

Target before the first element (0); Target after the last element (n).