出處： https://leetcode.com/problems/search-insert-position/
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
這次直接把思路寫在 code 上：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
// 最左邊的位置
let left = 0
// 最右邊的位置
let right = nums.length - 1
// 中間的數字
let idx = Math.ceil(right/2)
// 如果比第一個數字小，直接放最前面
if (target <= nums[left]) return 0
// 如果比最後一個數字大，直接方最後面
if (target > nums[right]) return nums.length
// 開始循環，一直到縮小範圍到兩個位置之間
while (right - left > 1) {
// 如果中間的數字大於要插入的數字，則範圍從右邊內縮
if (nums[idx] >= target) {
right = idx
} else {
// 如果中間數字小於要插入的數字，則範圍從左班內縮
left = idx
}
// 調整中間的位置
idx = left + Math.ceil((right - left) / 2)
}
return idx
};
