题目链接
https://leetcode-cn.com/problems/search-insert-position/
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 $O(logn)$ 的算法。
示例
示例 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
输出：-1
题解
在正常思路下只要遍历一次就能直接找到 target 项对应的索引，时间复杂度为 $O(n)$，但是题目要求时间复杂度 $O(logn)$，所以应该使用 二分查找法 来解决该问题。
什么是二分查找呢？举一个例子，就比如我们在英文字典查一个单词，翻开字典我们就能通过单词的开头字母确认在字典的前半部分还是后半部分，如果在前半部分，那么后半部分就都不需要查看了，重复这个动作直到找到单词所在的页码为止。
所以，使用二分查找的前提是，集合一定是有序排列的。
回到题目本身，想要从中间将数组一分为二则需要一个指针 mid 指向当前保留集合的中间（让值是整数通常向下取整），同时需要左右两个边界指针 left 和 right，并在每次查找时动态变更。
若数组中没有查找到 target，则 left 和 right 指针最终会 重合（最后一次移动左侧指针）或 交叉（最后一次移动右侧指针，且左侧指针和中间指针重合），所以插入的位置应为左侧指针（向下取整的情况下）的位置。
循环版本：
const searchInsert = (nums, target) => {
let left = 0;
let right = nums.length - 1;
let mid;
while (left <= right) {
mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
复杂度分析：
- 时间复杂度：$O(logn)$；
- 空间复杂度：$O(1)$。
大部分情况下循环和递归都可以互相转换，原因是循环体内部和递归的函数本身都是在解决一类问题的子问题。
递归版本：
const searchInsert = (
nums,
target,
left = 0,
right = nums.length - 1
) => {
if (left > right) return left;
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
return mid < nums[mid]
? searchInsert(nums, target, mid + 1, right)
: searchInsert(nums, target, left, mid - 1);
}
复杂度分析：
- 时间复杂度：$O(logn)$；
- 空间复杂度：在使用语言存在 尾递归 优化时为 $O(1)$，否则为 $O(logn)$。
