Search Insert Position

NeetCode: Search Insert Position · LeetCode: 35. Search Insert Position · Difficulty: Easy

Given a sorted array of distinct integers and a target value, return the index of the target if it is present. If it is not, return the index where it would be inserted to keep the array sorted.

Example

Text

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

The answer is the index of the first element that is >= target, or nums.length if there is none. That is the classic "lower bound".

Brute force: linear scan

Walk the array and stop at the first element that is not smaller than the target. If the loop finishes, every element is smaller and the target goes at the end. This does not use the sorted order and can touch every element.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1, 3, 5, 6};
        System.out.println(s.searchInsert(nums, 5));
        System.out.println(s.searchInsert(nums, 2));
        System.out.println(s.searchInsert(nums, 7));
        System.out.println(s.searchInsert(new int[] {}, 3));
    }
}

Output

Time: O(n). Space: O(1).

Optimal: binary search for the lower bound

Because the array is sorted, "is nums[i] >= target?" is false for a prefix and true for the rest. The answer is the first true. Keep a half-open range [lo, hi) that always contains the answer: if nums[mid] < target the answer is right of mid, otherwise mid itself could be the answer, so hi = mid. Starting with hi = nums.length (not length - 1) covers the "insert at the end" case and makes an empty array work with no special case.

hi	mid	nums[mid]	action (target 2)
4	2	5	5 >= 2, hi = 2
2	1	3	3 >= 2, hi = 1
1	0	1	1 < 2, lo = 1

The range is empty at lo = hi = 1, which is the answer.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1, 3, 5, 6};
        System.out.println(s.searchInsert(nums, 5));
        System.out.println(s.searchInsert(nums, 2));
        System.out.println(s.searchInsert(nums, 7));
        System.out.println(s.searchInsert(new int[] {}, 3));
        System.out.println(s.searchInsert(nums, 0));
    }
}

Output

Time: O(log n). Space: O(1).