Find the Insertion Index

Given a sorted array of integers, find the correct index to insert a target value so that the array remains sorted. This problem tests your ability to apply efficient search algorithms in common scenarios.

arraybinary searchsorted arraysearchalgorithm

Problem Statement

You are given a sorted array of integers, nums, and a target integer, target. Your task is to determine the index where the target should be inserted into the array such that the sorted order is maintained. If the target already exists in the array, return its index. Otherwise, return the index where it would be inserted.

Example 1

Input: nums = [2, 5, 7, 11, 15], target = 9

Output: 3

The target 9 does not exist in the array. It should be inserted between 7 and 11, which is at index 3.

Example 2

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

Output: 1

The target 2 does not exist in the array. It should be inserted between 1 and 3, which is at index 1.

Constraints

-1 <= nums.length <= 10^4
--10^4 <= nums[i] <= 10^4
-nums is sorted in ascending order
--10^4 <= target <= 10^4

Brute Force Approach

Imagine you're a librarian trying to find the right spot for a new book on a shelf. You'd start from the beginning, compare the book's title to each book on the shelf until you find a title that comes later, or reach the end. This linear search has a time complexity of O(n) and uses constant extra space O(1).

TimeO(n)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem