0035._Search_Insert_Position

发表于 分类于 ， ，

035. Search Insert Position

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Given a sorted array 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 may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

解题方案

思路 1
**- 时间复杂度: O(logN)**- 空间复杂度: O(N)**

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let searchInsert = function(nums, target) {
    let lo = 0,high = nums.length-1;
    while(lo<=high){
         let mid = Math.floor((high-lo)/2)+lo;
         if(nums[mid]===target)
             return mid;
         if(nums[mid]>target)
             high = mid-1;
         else lo = mid+1;
    }
    return lo;
};