前端算法之搜尋插入位置

給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。這就是搜尋插入位置算法。與二分算法很相似

示例 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

var searchInsert = function(nums, target) {
        let left = 0,right = nums.length -1 ,n = nums.length
            while (left <= right) {
                let mid = (left + right) >> 1
            if(nums[mid] >= target) {
                    // 值在左側
                    n = mid
                    right = mid - 1
            }else {
                // 右側
                left = mid + 1       
            }
            }
            return n
};      

解題如上。此題的解題方案如下：

1. 根據題頭我們可以知道這是一個排序好的數組。是以我們直接可以基于二分查找來進行坐。

2. 我們在數組中找到目标值，傳回其索引，跟之前二分查找的時候是一緻的。

3. 如果目标值不存在數組中，那麼傳回它會被插入的位置。這裡可以的了解就是，分為兩種，

• 第一種，target 的值是在數組中的，這時候我們利用二分可以找到最近的下标，傳回出去即可解答。
• 第二種，target的值不在數組中，也就是說數組中沒有。如何進行呢？

假設數組為： [1,2,3,4,5,6]  target 為 0 ，預設抛出的值 N  為 0

這樣的話，我們通過三次二分就可以發現1的坐标為0.即 我們找尋最接近的值的下标則為0.

但是如果我們的 target 為 7 呢。 這時候會發現測試用例走不過去了。

這是什麼願意呢？是因為，我們的target為7，則依舊需要三次二分。

第一次二分後的中間值是2，第二次4 ，第三次5.但是它依舊沒有找到位置。說明方法沒進入，這時候如果初始化 N 是 0 的話，則方法會直接傳回 0  造成錯誤。這時候大家明白了吧。