☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Search insert position

Easy TUF ID 89 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a sorted array nums of distinct integers and a value target. If target is in the array, return its index. Otherwise return the index at which target would have to be inserted so that the array stays sorted.

Constraints: 0 ≤ n ≤ 10^4, values and target fit in a 32-bit signed integer, all values distinct. The required running time is O(log n).

Example 1

nums = [1, 3, 5, 6], target = 5
answer = 2                // 5 is present at index 2

Example 2

nums = [1, 3, 5, 6], target = 2
answer = 1                // 2 is absent; inserting at index 1 gives [1, 2, 3, 5, 6]

Example 3

nums = [1, 3, 5, 6], target = 7
answer = 4                // larger than everything: append at index n

Both cases of the statement collapse into one sentence: return the smallest index i with nums[i] >= target, or n if none exists. If target is present, that first index >= target is exactly where it sits (values are distinct). If it is absent, that index is the first element bigger than it, which is exactly where it must be inserted. So this problem is the lower bound in disguise.

Approach 1: Brute force, linear scan

Intuition. Walk from the left until the first element that is >= target. If it equals target, that is where the target lives; if it is greater, that is the insertion point. If we run off the end, insert at n.

Algorithm.

  1. For i from 0 to n - 1: if nums[i] >= target, return i.
  2. Return n.
static int bruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] >= target) return i;
    }
    return nums.length;
}

Complexity. Time O(n), space O(1). Correct, but the problem explicitly asks for logarithmic time.

Approach 2: Optimal, binary search for the lower bound

Intuition. The predicate nums[i] >= target is false on a prefix and true on the remainder of the sorted array. We want the first true. Binary search on a monotone predicate: probe mid; if it is true, remember it and look left for an earlier true; if false, look right. Start ans at n so that the “no true anywhere” case needs no special handling.

Algorithm.

  1. lo = 0, hi = n - 1, ans = n.
  2. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If nums[mid] >= target: ans = mid, hi = mid - 1.
    • Else lo = mid + 1.
  3. Return ans.
static int optimal(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1, ans = nums.length;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) {
            ans = mid;            // mid works; a smaller index may also work, so look left
            hi = mid - 1;
        } else {
            lo = mid + 1;         // nums[mid] < target, so target belongs after mid
        }
    }
    return ans;
}

Dry run on nums = [1, 3, 5, 6], target = 2:

lo hi mid nums[mid] nums[mid] >= 2? action
0 3 1 3 yes ans = 1, hi = 0
0 0 0 1 no lo = 1
1 0     lo > hi return 1

Complexity. Time O(log n), space O(1).

The method never checks for equality. It does not need to: when target is present, the first index with nums[i] >= target is the target’s own index, because distinct values mean no smaller index can hold a value >= target without being strictly greater, and strictly greater values come after the target in sorted order.

Approach 3: Optimal, classic binary search that returns lo on a miss

Intuition. Take the ordinary “find target” binary search and ask what the pointers look like when it fails. The loop ends with hi == lo - 1. Every index we moved lo past held a value < target, and every index we moved hi below held a value > target. So after the loop, nums[hi] < target < nums[lo] (where the two sides are understood as “nothing” when hi = -1 or lo = n). That is precisely the definition of the insertion point: lo. If the search does find target, we return its index directly.

This approach is worth knowing because it explains a fact many people use without proof: a failed binary search leaves lo at the insertion point. It is the same convention behind Java’s Arrays.binarySearch, which returns -(insertionPoint) - 1 on a miss.

Algorithm.

  1. lo = 0, hi = n - 1.
  2. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If nums[mid] == target, return mid.
    • If nums[mid] < target, lo = mid + 1; else hi = mid - 1.
  3. Return lo.
static int optimalClassic(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return lo;                    // here hi == lo - 1: nums[hi] < target < nums[lo]
}

Dry run on nums = [1, 3, 5, 6], target = 7:

lo hi mid nums[mid] comparison action
0 3 1 3 3 < 7 lo = 2
2 3 2 5 5 < 7 lo = 3
3 3 3 6 6 < 7 lo = 4
4 3     lo > hi return 4

Complexity. Time O(log n), space O(1).

Why is lo and not hi the right value to return? Consider the invariant that holds at the start of every iteration: all indices < lo hold values < target, and all indices > hi hold values > target. Initially both sets are empty, and each update preserves it. When the loop exits with lo = hi + 1, the two sets together cover the whole array: indices 0..lo-1 are < target and indices lo..n-1 are > target. Inserting at lo keeps the array sorted.

Edge cases and pitfalls