35\. Search Insert Position

# 35. Search Insert Position (opens new window)

# Description

Difficulty: Easy

Related Topics: Array (opens new window), Binary Search (opens new window)

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
1
2

Example 2:

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

Example 3:

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

Constraints:

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

# Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 * 1.二分查找
 * 先设定左侧下标left和右侧下标right,再计算中间下标mid
 * 每次根据nums[mid]和target之间的大小进行判断,相等则直接返回下标,nums[mid] < target 则 left 右移,nums[mid] > target 则 right 左移
 * 查找结束如果没有相等值则返回 left, 该值为插入位置
 */
var searchInsert = function(nums, target) {
    let [left, right] = [0, nums.length - 1];
    
    while (left <= right) {
        const mid = (left + right) >>> 1;
        if (nums[mid] === target) return mid;
        
        if (nums[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    
    return left;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
上次更新: 2022/7/14 下午7:06:25