Search Insert Position

Given a sorted array of distinct integers and a target, return the index of the target if it is in the array. If it is not, return the index where it would be inserted to keep the array sorted. The solution must run in O(log n). This is LeetCode 35.

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

How to Think About It

Step 1: Both answers are the same question

If the target is present, its index is the first position holding a value that is at least the target. If it is absent, it would be inserted in front of the first larger value, which is again the first position holding a value at least the target. So both cases ask for one thing: the first index where nums[i] >= target.

Step 2: That position is a boundary

For [1, 3, 5, 6] and target 2, test "is nums[i] >= 2?" at each index: false, true, true, true. The answer is where false turns into true, index 1. Finding such a boundary is what the "first true" binary search does.

Step 3: The answer can be past the end

For target 7 every test is false, and the answer is 4, the length of the array. So the search range is [0, n], not [0, n - 1]: set hi = nums.length.

Step 4: Never throw away a possible answer

  • If nums[mid] < target, mid is too small, and so is everything before it: lo = mid + 1.
  • Otherwise mid might be the answer, so keep it: hi = mid, not mid - 1.
  • Stop when lo == hi: only one candidate is left, and it is the answer.

Walkthrough

Target 2 in [1, 3, 5, 6]:

lohimidnums[mid]Decision
04255 >= 2: could be the answer, hi = 2
02133 >= 2: hi = 1
01011 < 2: lo = 1
11lo == hi: answer 1

Java Solution

The loop uses lo < hi together with hi = mid. Mixing lo <= hi with hi = mid would loop forever once lo == hi.

Java
public class SearchInsertPosition {

    // Returns the first index whose value is >= target (the "lower bound")
    public static int searchInsert(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length;                // the answer can be nums.length: insert at the end
        while (lo < hi) {                    // stop when lo == hi: one candidate left
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) {
                lo = mid + 1;                // mid is too small, so the answer is after it
            } else {
                hi = mid;                    // mid could be the answer, keep it in the range
            }
        }
        return lo;
    }

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

The original implementation, SearchInsertPosition.java, is on GitHub. This function is often called lower bound; C++ has it as std::lower_bound, and Java's Arrays.binarySearch returns -(insertion point) - 1 for missing values, which encodes the same answer.

Complexity

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

The same lower-bound search finds both ends of a run of equal values in Find First and Last Position.