Search Insert Position

Leetcode Problem 35: Search Insert Position

Problem Summary

Given a sorted array of distinct integers and a target value, return the index where the target is found. If the target is not in the array, return the index where it would need to be inserted to keep the array sorted.

Your solution must run in O(log n) time.

Constraints:

• The array has between 1 and 10,000 elements.
• Array values and the target are integers in the range [-10,000, 10,000].
• All values in the array are distinct and sorted in ascending order.

Techniques

• Array
• Binary Search

Solution

function searchInsert(nums: number[], target: number, left: number = 0, right: number = nums.length): number {
    if (left >= right) {
        return left
    }

    const mid = left + Math.floor((right - left) / 2)
    
    if (nums[mid] === target) {
        return mid
    }

    if (target < nums[mid]) {
        return searchInsert(nums, target, left, mid)
    } else {
        return searchInsert(nums, target, mid + 1, right)
    }
};

console.log(searchInsert([1, 3, 5, 6], 5)) // Output: 2