给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

    请必须使用时间复杂度为 O(log n) 的算法。

    示例 1:

    输入: nums = [1,3,5,6], target = 5
    输出: 2
    示例 2:

    输入: nums = [1,3,5,6], target = 2
    输出: 1
    示例 3:

    输入: nums = [1,3,5,6], target = 7
    输出: 4

    1. /**
    2.  * @param {number[]} nums
    3.  * @param {number} target
    4.  * @return {number}
    5.  */
    6. var searchInsert = function (nums, target) {
    7.     // if (nums.length === 0) return 0;
    8.     // // 大于等于目标值时直接返回下标，大于就直接取代，等于就返回
    9.     // for (let i = 0; i < nums.length; i += 1) {
    10.     //     if (nums[i] >= target) {
    11.     //         return i
    12.     //     } else if (nums[nums.length - 1] < target) {
    13.     //         // 小于直接插入末尾
    14.     //         return nums.length
    15.     //     }
    16.     // }
    17.     // 二分法
    18.     let n = nums.length;
    19.     let l = 0, r = n - 1;
    20.     while (l <= r) {
    21.         let mid = (l + r) >> 1;
    23.         if (nums[mid] > target) {
    24.             // target 在左区间，所以[l, mid - 1]
    25.             r = mid - 1
    26.         } else if (nums[mid] < target) {
    27.             // target 在右区间，所以[middle + 1, right]
    28.             l = mid + 1
    29.         } else {
    30.             return mid
    31.         }
    32.     }
    33.     return r + 1
    34. };

    image.png