Constfunction searchInsert(nums: number[], target: number): number {
// 按题目意思其实就是找有序数组当中第一个>=target的数
return lowerBound(nums, target);
};
// 在nums中二分查找第一个>=target，找到返回下标
function lowerBound(nums: number[], target: number): number {
// 左闭右开
let l = 0;
let r = nums.length;
while (l < r) {
const m = Math.floor((l + r) / 2);
// left---target---mid---right
if (nums[m] >= target) {
r = m;
}
// left---mid---target---right
else {
l = m + 1;
}
}
return r;
}
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1：
输入：
nums = [1,3,5,6],target = 5输出：
2示例 2：
输入：
nums = [1,3,5,6],target = 2输出：
1示例 3：
输入：
nums = [1,3,5,6],target = 7输出：
4示例 4：
输入：
nums = [1,3,5,6],target = 0输出：
0示例 5：
输入：
nums = [1],target = 0输出：
0提示：
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4