35. Search Insert Position (搜索插入位置)
更新於 2024/05/09閱讀時間約 1 分鐘
↑看個小廣告，支持好內容↑
給定的陣列已經 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
留言0
查看全部
你可能也想看
Google News 追蹤
*合作聲明與警語：
本文係由國泰世華銀行邀稿。
證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務，定期定額(股)服務由國泰綜合證券提供。
剛出社會的時候，很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天，都會聽到各種市場動態、理財話題，像是：聯準會降息或是近期哪些科
題目 : 35. Search Insert Position
這次面試是在吉比特的官網投了大概一小時内，就有HR加我微信聯絡我，約面試和所有視頻都會在微信溝通，讓應聘者有滿滿的安全感，整體面試流程在三星期内完成，無論哪一關難易度都沒有太多落差，所有的面試官也都很積極的在和應聘者互動、反饋，解答問題也都非常仔細有耐心，面試感受給予最高五星好評！
根據日本《學校教育法》規定，外國人學校和駕訓班一樣同屬「各種學校」，這些外國人學校附屬的幼托機構也是「各種學校」。結果就出現了將孩子送到未經地方政府認可的「認可外保育施設」可以領到補助，但把孩子送到外國人學校的幼兒園，卻完全領不到補助⋯⋯
伴隨今年 10月1日「一國兩稅制」的日本消費稅新制上路，日本政府也在同一天正式推出「幼保無償化」。簡單來說，就是將消費稅從 8%調漲到 10%當中多出來的 2%稅收，用來補助家有 3–5歲學齡前幼童的幼托費用，或是家有 0–2歲嬰幼兒的低收入戶（住民税非課税世帯）可以免費將孩子送到幼稚園或保育所。
「幼保無償化」擴大適用範圍到「認可外保育施設」後，就失去了原先希望藉機淘汰劣質私托機構的目的，只會讓絕大多數家有 3–5歲學齡前兒童的家長感到開心而已。
靜謐的祭壇深處，有三個人，一位是僵在原地無法動彈的尷尬男性，再一位是正在地上打滾笑個不停的美麗男性，最後一位是試圖挽回局面卻越搞越糟的無奈女性。
你想當菁英嗎？
在這部電影中，似乎一職暗喻著現在社會的黑暗面。若是要你放棄你的自尊，才能到達所謂的高階區，你願意放棄嗎？還是你會選擇在平民區安貧樂道。
宗教信仰以事實為依據，但是不同的信徒對事實的依賴程度不同。許多神學家、信徒面對不合科學、不合事實的批評，尤其神存在的論證，不但大聲反駁，還挖空心思來對招。可見他們真的在乎宗教說法的真假，而不只是把宗教說法當成心裡受用的虛構故事。神學家常兩面討好，面對學者就說是寓意，面對平信徒就說是事實。
*合作聲明與警語：
本文係由國泰世華銀行邀稿。
證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務，定期定額(股)服務由國泰綜合證券提供。
剛出社會的時候，很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天，都會聽到各種市場動態、理財話題，像是：聯準會降息或是近期哪些科
題目 : 35. Search Insert Position
這次面試是在吉比特的官網投了大概一小時内，就有HR加我微信聯絡我，約面試和所有視頻都會在微信溝通，讓應聘者有滿滿的安全感，整體面試流程在三星期内完成，無論哪一關難易度都沒有太多落差，所有的面試官也都很積極的在和應聘者互動、反饋，解答問題也都非常仔細有耐心，面試感受給予最高五星好評！
根據日本《學校教育法》規定，外國人學校和駕訓班一樣同屬「各種學校」，這些外國人學校附屬的幼托機構也是「各種學校」。結果就出現了將孩子送到未經地方政府認可的「認可外保育施設」可以領到補助，但把孩子送到外國人學校的幼兒園，卻完全領不到補助⋯⋯
伴隨今年 10月1日「一國兩稅制」的日本消費稅新制上路，日本政府也在同一天正式推出「幼保無償化」。簡單來說，就是將消費稅從 8%調漲到 10%當中多出來的 2%稅收，用來補助家有 3–5歲學齡前幼童的幼托費用，或是家有 0–2歲嬰幼兒的低收入戶（住民税非課税世帯）可以免費將孩子送到幼稚園或保育所。
「幼保無償化」擴大適用範圍到「認可外保育施設」後，就失去了原先希望藉機淘汰劣質私托機構的目的，只會讓絕大多數家有 3–5歲學齡前兒童的家長感到開心而已。
靜謐的祭壇深處，有三個人，一位是僵在原地無法動彈的尷尬男性，再一位是正在地上打滾笑個不停的美麗男性，最後一位是試圖挽回局面卻越搞越糟的無奈女性。
你想當菁英嗎？
在這部電影中，似乎一職暗喻著現在社會的黑暗面。若是要你放棄你的自尊，才能到達所謂的高階區，你願意放棄嗎？還是你會選擇在平民區安貧樂道。
宗教信仰以事實為依據，但是不同的信徒對事實的依賴程度不同。許多神學家、信徒面對不合科學、不合事實的批評，尤其神存在的論證，不但大聲反駁，還挖空心思來對招。可見他們真的在乎宗教說法的真假，而不只是把宗教說法當成心裡受用的虛構故事。神學家常兩面討好，面對學者就說是寓意，面對平信徒就說是事實。