035. Search Insert Position
难度: Easy
刷题内容
原题连接
- https://leetcode.com/problems/search-insert-position/
内容描述
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)***
代码：
/**
* @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;
};
