35. Search Insert Position (搜索插入位置)

英文版點我｜中文版點我

↑看個小廣告，支持好內容↑

給定的陣列已經 sorted，又要求 O(logn) 執行完，沒有懸念就是 Binary Search 了，我們先套上大致的模板看看：

let left=0, right=nums.length-1;

while(left<right){
    let mid=left+Math.floor((right-left)/2);
    // 如果中間項仍小於目標，左半邊都不用找了
    if(nums[mid]<target){
        left=mid+1;
    }else{
        right=mid;
    }
}

接下來才是重點，思考看看：這樣輸出的 left 會代表什麼？

left 代表的是「首個不小於目標的 index 值」，假設第一項就大於目標，自然插入的位置為 0，如果剛好等於目標，根據題意我們也要輸出 0，到這都沒問題。

考慮另一種極端狀況，要是最後一項都還小於目標呢？

nums=[1,3,5,6], target=7  // 輸出: 4​

那就形同要在陣列多 push 一項，而這和 left 回傳給我們的 3 不符了。

二分搜尋很常敗在這種邊界條件，請務必釐清 return 值是否滿足題意以及各種你舉得出的狀況 XD

• 本題分類標籤：Array、Binary Search
• 本題正解率＝45.6％

❤️ 若內容對你實用，歡迎追蹤本專題，或小額贊助支持～
⭐ 這是我的第 22 篇刷題筆記，完整解題索引看這裡 → Here