Code Logo

Search Insert Position

Published at05 Jan 2026
Created by
Easy 15 views
Like21

You are given a sorted array and a target value. If the target already exists, return its index. If it does not exist, return the index where it should be inserted so the array would still stay sorted.

That means the answer is the first position where the target could fit without breaking the order. Sometimes that position is in the middle, and sometimes it is all the way at the front or the end.

For example, if nums = [1,3,5,6] and target = 5, the answer is 2 because 5 is already there. If target = 2, the answer is 1 because 2 should go between 1 and 3. If target = 7, the answer is 4 because it belongs after the last value.

So the task is to find the first index where the value is greater than or equal to the target.

Example Input & Output

Example 1
Input
nums = [1,3,5,6], target = 5
Output
2
Explanation

The number 5 already exists in the list and is located at index 2.

Example 2
Input
nums = [1,3,5,6], target = 2
Output
1
Explanation

The target 2 is not in the list but would fit between 1 and 3, so its position would be index 1.

Example 3
Input
nums = [1,3,5,6], target = 7
Output
4
Explanation

The target 7 is greater than all elements, so it should appear at the end, which corresponds to index 4.

Algorithm Flow

Recommendation Algorithm Flow for Search Insert Position
Recommendation Algorithm Flow for Search Insert Position

Solution Approach

This is a classic lower bound binary search. We want the first index where nums[i] >= target.

If the target exists, that search lands on its first position. If the target does not exist, that same position is exactly where it should be inserted.

let left = 0;
let right = nums.length;

while (left < right) {
  const mid = Math.floor((left + right) / 2);
  if (nums[mid] >= target) {
    right = mid;
  } else {
    left = mid + 1;
  }
}

When the loop ends, left is the correct answer. It works whether the target is already present or not.

This solution takes O(log n) time and O(1) extra space.

Best Answers

java
class Solution {
    public int search_insert(Object nums, Object target) {
        int[] arr = (int[]) nums;
        int t = (int) target;
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < t) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}