Search Insert Position

Search Insert Position

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

First Try

Given the O(log n) runtime complexity, we should use binary search. First think about normal binary search,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function BinarySearchFirst(arr, target) {
    if (arr.length <= 1) return -1
    let lowIndex = 0
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            if (midIndex === 0 || arr[midIndex - 1] < target) 
            return midIndex
            highIndex = midIndex - 1
        }
    }
    return -1
}

we need to make adjustment on last return, when highIndex < = lowIndex, it means we can’t find a number equal to target, then we need to insert the target into the array, position will either be lowIndex or lowIndex+1.
The final submission is below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let start = 0 
    let end = nums.length-1
    
    while(end > start){
    let mid = Math.floor((end+start)/2)
    if (nums[mid] === target){
        return mid
    }else if(nums[mid] < target){
        start = mid+1
    }else{
        end = mid-1
    }
    }
    if(nums[start]< target){
        return start+1
    }else{
        return start
    }
 
};

Runtime: 72 ms, faster than 80.09% of JavaScript online submissions for Search Insert Position.
Memory Usage: 40 MB, less than 12.53% of JavaScript online submissions for Search Insert Position.

• ← Previous Post
• Next Post →