leetcode：搜索插入位置

描述：

题解：

查找算法，并且时间复杂度为*O(log n)*，这个不用多想就是二分查找了。

二分查找的算法思路比较简单，使用 while 循环折半查找，比如：1 ~ 100

let low = 0
let high = list.length - 1

在 while 循环里每次都检查中间的元素，首先猜 50。如果刚好是 50，就直接返回。
如果猜的字数小了，就应该把 low 改为 mid + 1，high 不变

如果猜的字数大了，就应该把 high 改为 mid -1，low 不变

...

一直这样缩小范围，直到找到。所以 while 的条件应该是 low <= high

具体实现：

function searchInsert(nums, target) {
  let low = 0
  let high = nums.length - 1
  let mid
  while (low <= high) {
    // 向下取整
    mid = Math.floor((low + high) / 2)
    //nums[mid]为你猜的数字
    if (nums[mid] == target) {
      return mid
    }

    if (nums[mid] > target) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return low
}