Search Insert Position

EASY

Description

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.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

Approaches

Checkout 2 different approaches to solve Search Insert Position. Click on different approaches to view the approach and algorithm in detail.

Linear Scan

This approach involves iterating through the array from the beginning to find the target or its insertion point. It's straightforward but less efficient.

Algorithm

Iterate through the array nums from index i = 0 to n-1.
For each element nums[i], check if it is greater than or equal to the target.
If nums[i] >= target, return the current index i.
If the loop completes, it means the target should be inserted at the end. Return the length of the array.

We can traverse the array nums with a single loop. For each element nums[i], we compare it with the target. If nums[i] is greater than or equal to the target, we've found the correct position. This is because the array is sorted, so any subsequent element will also be greater. If we find such an element, we return its index i. If the loop finishes without finding any element greater than or equal to the target, it implies that the target is larger than all elements in the array. In this case, the correct insertion position is at the very end of the array, so we return the length of the array.

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Simple to understand and implement.
Works correctly for all cases.

Cons:

Inefficient for large input arrays.
Does not meet the O(log n) time complexity requirement specified in the problem description.

Code Solutions

Checking out 4 solutions in different languages for Search Insert Position. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Search Insert Position

Algorithms:

Binary Search

Data Structures:

Array

Companies:

Adobe |Amazon |Apple |Bloomberg |