Search Insert Position

easy binary search

Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Standard lower-bound binary search: maintain [lo, hi). While lo < hi, look at mid: if nums[mid] < target, push lo to mid + 1; else pull hi to mid. The final lo is the smallest index whose value is ≥ target — exactly the insertion point.

Inputnums = [1, 3, 5, 6], target = 5

Output2

Target 5 sits at index 2. For target 4 the answer would be 2 (insert before 5); for 7 it's 4 (append).

sorted nums

target

def search_insert(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target: lo = mid + 1
        else: hi = mid
    return lo

function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

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) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int searchInsert(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Explanation

We want the index where the target sits, or where it would be inserted to keep the array sorted. Both cases are the same question: find the first position whose value is at least the target. This is the classic lower-bound binary search.

We keep a half-open window [lo, hi) with hi = nums.length, so hi can legally point one past the end — that is what lets the answer be "append at the end" when the target is bigger than everything.

While lo < hi, we look at mid: if nums[mid] < target, the insertion point must be to the right, so lo = mid + 1. Otherwise nums[mid] >= target could itself be the answer, so we pull hi = mid without discarding it. When the window closes, lo is the answer.

Example: nums = [1,3,5,6], target 5. The search converges on index 2, where 5 lives. For target 4 it returns 2 as well (insert before 5), and for 7 it returns 4 (append at the end).

Each step halves the range, so the insertion point is found in about log n comparisons.

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