题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例：
输入: [1,3,5,6], 0
输出: 0
思想
- 因为是有序的数组，所以我们可以使用二分法找到插入的位置
代码
var searchInsert = function(nums, target) {
// 二分查找
let left = 0;
let right = nums.length - 1;
while(left < right) {
let m = Math.floor( (right + left) / 2 );
if(nums[m] == target) {
return m;
}
if(target < nums[m]) {
right = m - 1;
} else {
left = m + 1;
}
}
let mid = Math.floor((right + left) / 2);
mid = mid > 0 ? mid : 0; // 为了解决负数问题
// 最后我们已经知道了左边跟右边的边界了，然后我们用target 比对一下 nums[mid] 就知道是放在当前位置还是放在后面一个位置了
return target > nums[mid] ? mid + 1 : mid ;
};