↑看個小廣告，支持好內容↑
給定的陣列已經 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
