35. Search Insert Position Easy

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

Approach

Input: An ascending sorted array nums, and a target value.

Output: Return the index of the target value, or the index where it should be placed if it doesn't exist.

This problem belongs to the Basic Search category.

We can use binary search to quickly find the target value.

Every time nums[mid] < target, the left pointer moves to mid + 1, which means we exclude all numbers less than target. Every time nums[mid] > target, the right pointer moves to mid - 1, which means we exclude all numbers greater than target.

When the target does not exist in the array, the left pointer will stop at the first location immediately to the right of all the numbers that are less than target, which is exactly where target should be placed.

Implementation

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # Initialize left and right pointers
        l, r = 0, len(nums) - 1

        # Binary search
        while l <= r:
            mid = (l + r) // 2  # Calculate the middle position

            if nums[mid] < target:
                # Target value is in the right half, move left pointer
                l = mid + 1
            elif nums[mid] > target:
                # Target value is in the left half, move right pointer
                r = mid - 1
            else:
                # Target value found, return its index
                return mid

        # Target value not found, l is the position where the target should be inserted
        return l

javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }

    return left;
};

Complexity Analysis

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

Links

35. Search Insert Position (English)

35. 搜索插入位置 (Chinese)