給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為?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 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums?為?無重復元素?的?升序?排列數組
• -104 <= target <= 104

思路：如果題目沒有限制時間復雜度的話，那么用for循環可以很簡單的實現，由于該題目需要的時間復雜度為O(log n)所以這里使用二分查找，二分查找分別有遞歸和迭代兩種方式，這里使用迭代來實現

二分查找的核心變量有三個：left指針、right指針和mid（middle）指針，每次將target與數組中間項（Arr[mid]）作比較，target大于Arr[mid]，將left指針右移至mid位置，重新計算mid指針位置target小于Arr[mid]，將right指針左移至mid位置，重新計算mid指針位置

mid=Math.floor(left+(right-left)/2)

下面附上實現代碼

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var searchInsert = function (nums, target) {let left = 0let right = nums.length - 1while (left <= right) {let mid = Math.floor(left + (right - left) / 2);if (target == nums[mid]) {return mid}else if (target < nums[mid]) {right = mid - 1} else {left = mid + 1}}return right + 1
};