Search Insert Position

Problem

Given a sorted array nums and a target target, return the index where target should be inserted to keep the array sorted.

If target already exists, return its current index.

Intuition

This is not a different problem from #704. It is the lower bound version of binary search: find the first position where nums[i] >= target.

That phrasing is useful because it removes the ambiguity around "found vs not found." Whether target is already present or not, the lower bound gives the right answer. If the value exists, that first >= position is its index; if it does not, it is the insertion point.

Again, a half-open interval [lo, hi) keeps the invariant clean.

Approach

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut lo = 0usize;
        let mut hi = nums.len();

        while lo < hi {
            let mid= lo + (hi - lo) / 2;
            if nums[mid] < target {
                lo= mid + 1;
            } else {
                hi= mid;
            }
        }

        lo as i32
    }
}

function searchInsert(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }

  return lo;
}

Trace

Insert target = 2 into nums = [1, 3, 5, 6]:

The loop ends with lo = 1, which is the correct insertion point.

Edge cases

• Target already exists — lower bound returns its leftmost position, which is exactly the required index for this problem because the array has distinct values.
• Insert at the front — if target is smaller than every element, lo stays at 0.
• Insert at the end — if target is larger than every element, lo becomes nums.len().

Takeaway

"Find the first place something becomes true" is the lower-bound pattern. It shows up in insertion points, first bad versions, and many optimization checks.

If #704 is "search for equality," #35 is "search for the boundary."