LeetCode 35.搜索插入位置

https://leetcode.cn/problems/search-insert-position
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

思路：
如果可以找到一个索引 i 使 nums[i] = target，则返回i
如果不能找到一个索引，那么应该返回索引 i 使 num[i - 1] < target < num[i]
综上，需要找一个 i，使num[i - 1] < target <= num[i]
可以用二分法的思路来进行处理：
如果nums[middle] < target，说明包括middle及其左边的值全部不是需要的索引，需要把left = middle + 1;
而nums[middle] >= target的情况，那么 middle 可能是需要的索引，而middle的右边一定不是需要的索引。如果middle的左边不存在所需索引，那么middle就是要找的值，所以下一轮的搜索区间是[left，middle]，即设置 right = middle。
首先left = 0，而right = nums.length，因为nums.length也可能是所需索引。
在区间[left，right] 中一定存在所需的索引，最后退出循环的时候一定有left = right，所以循环终止的条件是while (left < right)，最终返回left或right都可以。

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        let middle = left + ( (right - left) >> 1);
        if (target > nums[middle] ) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }
    return right;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14