搜索插入位置
WangScaler: 一个用心创作的作者。声明：才疏学浅，如有错误，恳请指正。
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
分析
初步思考
因为是个已经排好序的数组，在里面寻找目标值，首先想到的就是家喻户晓的二分法。每次查找中间的值，每轮减少一半的遍历。这时候的时间复杂度，恰好就是O(log n)，也满足题目要求
继续思考
要写二分法，关键的就是要找中间的数的位置。
假设我们的数组长度是5。则第三个是我们的中间位置，也就是下标为2。(0+5-1)/2=2。
假设我们的数组长度是6。则第三或第四个是我们的中间位置，也就是下标为2或3。(0+6-1)/2=3。
我们有三个指针，一个指向头指针，一个指向尾指针，另一个自然就是我们中间指针。当中间的指针的值不是我们目标值且大于我们的目标值，我们就将尾指针变为中间指针的位置 -1；当中间的指针的值不是我们目标值且小于我们的目标值，我们就将头指针变为中间指针的位置+1；直到头指针大于等于尾指针还没找到，那么目标值必然插入到当前位置的后一个位置，如果找到了，自然不必说，返回下标即可。
答案
public static int searchInsert(int[] nums, int target) {
int first = 0;
int end = nums.length - 1;
while (first <= end) {
int mid = (end + first) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
end = mid - 1;
}
if (nums[mid] < target) {
first = mid + 1;
}
}
return first;
}复杂度
- 时间复杂度：O(logn)，其中 n 为数组的长度。
- 空间复杂度：O(1)。我们只需要常数空间存放三个指针的位置。
总结
这个题就是个简单的二分法，二分法是个典型的算法。
画个图，简单理解下，有序数组[1,2,3,4,5,6],目标值5。
- 第一轮，头节点在0的位置，尾节点在5的位置，中间节点在2的位置。对比3小于目标值5。
- 第二轮，移动头节点到中间节点+1的位置3。移动中间节点到(3+6-1)/2=4。对比就是目标值返回下标4。
都来了，点个赞再走呗！关注WangScaler，祝你升职、加薪、不提桶！
