題目連結:
題目意譯:
給定一個已排序的陣列 nums 以及一個目標值 target,回傳 target 在 nums 中的位置之索引值(如果有的話)。如果不在 nums 裡,則回傳 target 應插入於哪個位置才保持陣列的已排序性。
可以保證陣列中沒有重複的值。
範例測資:
範例 1:
輸入: [1,3,5,6], 5
輸出: 2
範例 2:
輸入: [1,3,5,6], 2
輸出: 1
範例 3:
輸入: [1,3,5,6], 7
輸出: 4
範例 4:
輸入: [1,3,5,6], 0
輸出: 0
解題思維:
利用二分搜尋法(Binary Search)找到最接近 target 但是要大於等於 target 的數字之索引值。如果是大於 target,則該數的索引值即是所求(因為是要找插入的位置)。如果該數剛好等於 target ,則其索引值也是所求(因為是要找 target 在的位置)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。