Code Logo

Search Insert Position

Published at05 Jan 2026
Created by
Easy 29 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

Solution Approach

Find the index where a target value should be inserted in a sorted array to maintain order. Use binary search. Maintain left and right bounds. At each step, compute mid. If nums[mid] equals target, return mid. If nums[mid] is less than target, search right half. Otherwise, search left half. When the loop ends, left is the insertion position.

function searchInsert(nums, target) {
  var left = 0, right = nums.length - 1;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return left;
}

Binary search narrows the range. When the target is not found, left points to the first element greater than target, which is the correct insertion index.

Time complexity is O(log n), space complexity is O(1).

Best Answers

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