题目
https://leetcode-cn.com/problems/search-insert-position
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 7
输出: 4
常规遍历
首先我们可能会想到遍历数组，找到合适的位置，返回下标。
是没错，这么做很简单。
因为是升序数组，我们自左往右遍历，如果比目标值小或者等于目标值，直接返回当前下标即可；如果遍历结束都未满足条件，那说明目标值比任意一个数组元素都大，所以返回数组长度。
var searchInsert = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) {
return i;
}
}
return nums.length;
};
好，提交！通过！但是貌似少点东西，仔细看题目，“请必须使用时间复杂度为 O(log n) 的算法。” 很显然我们直接遍历时间复杂度为O(n)，并不符合题目要求。
二分查找
时间复杂度O(log n)，那就明示我们使用二分查找了。
二分查找顾名思义体现一个二分，从数组的中间位置将数组分成两部分；
具体实现时需要两个下标（left, right）来框定数组的范围。中间值我们定义为 mid，mid = (left + right) >> 1（首位之和按二进制右移一位相当于除以二向下取整）。
比较中间位置和目标值，如果相等，那直接返回中间下标；
如果中间位置小于目标值，重新框定范围，取数组右半边，left = mid + 1，right 不变；
反之，取数组左半边，right = mid - 1，left 不变；
最后当 left 比 right 大的时候，说明数组中并不存在目标值（如果存在我们上面早就return掉了），而且当前位置肯定是目标值的合适插入位置，那这个插入位应该怎么取呢？是 left 还是 right ？
首先明确一点，当 left 变得比 right ，有两种情况：
1、left = mid + 1，导致 left > right
2、right = mid - 1，导致 right < left
但在这之前，left 和 right是相等的，他们之和除以2也和他们相等，这时候比较中间值和目标值，如果目标值大，那目标值插入的位置要靠后一位(+1)，于此同时按照上面的逻辑我们的left+1；否则就在当前位置插入即可，此时我们的left不变。
所以最终结论是：直接返回 left 即可。
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while(left <= right) {
let mid = (left + right)>>1;
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
};
