22. Search Insert Position · DSA Practice

nums is sorted with distinct values. Return the index of target if found; otherwise return the index where it would be inserted to keep the order.

Example 1

Input: nums = [1,4,6,9], target = 6

Output: 2

Example 2

Input: nums = [1,4,6,9], target = 5

Output: 2

Hint 1

You are looking for the first index whose value is ≥ target (the “lower bound”).

Binary Search

Approach 1: Lower-bound binary search ✅

Keep the half-open range [lo, hi) and converge on the first value ≥ target.

⏱ Time O(log n)💾 Space O(1)

Reference solution for Lower-bound binary search (time O(log n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)           # search in [lo, hi)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid                # nums[mid] >= target could be the answer
        return lo                       # first index with nums[i] >= target

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

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();  // first >= target
    }
};

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

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Binary Search.