35. 搜索插入位置
35. 搜索插入位置
分析
看提示，升序且无重复元素，要求算法复杂度为
- 在数组中找到目标值，并返回其索引。这个差不多直接告诉你用二分法。
- 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。我们来分析这个需求。
如果目标值不在数组中，但是：
- 在数组的两个元素中间，我们用二分法得到的是什么？
- 首先确定我们要找的是哪个位置？例如数组是
1，3，我们的目标值是 2，那么 3 所在的位置，就是我们要插入 2 的位置，也就是大于目标值的第一个位置。 - 首先我们分析一下当目标元素在数组中的时候，二分法的过程：通过循环，缩短
[start,end]这个区间，我们可以保证目标严肃一定在[start,end]这个区间之内，但是当目标元素不在数组中而是在相邻两个元素（比如 AB，且A<B）之间的时候，[start,end]这个区间首先会坍缩成一个点，即start==end，此时 start 和 end 都处在目标值的一边（任意一边都有可能），此时获取 mid，然后比较nums[mid]和目标值，会造成start > end，最终跳出 while 循环，此时，start 就是我们要找的值。这一段其实比较抽象，我也没想好用什么样的逻辑来讲解。
- 首先确定我们要找的是哪个位置？例如数组是
- 目标值小于数组的第一个元素，我们用二分法得到的是什么？
- start 一直为 0，end 一直减少，直到为 -1，此时 start 的位置就是我们需要返回的位置。
- 目标值大于数组的第一个元素，我们用二分法得到的是什么？
- end 一直为 0，start 一直增加，直到为 nums.length，此时 start 的位置就是我们需要返回的位置。
可以看到 start 指向的就是大于目标值的第一个位置。这样结果就很简单了。
- end 一直为 0，start 一直增加，直到为 nums.length，此时 start 的位置就是我们需要返回的位置。
public int searchInsert(int[] nums, int target) {
int start =0,end = nums.length-1;
while(start<=end){
int mid = start + (end - start)/2;
if(nums[mid] == target){
return mid;
}else if (nums[mid] < target){
start = mid +1;
}else if (nums[mid] > target){
end = mid - 1;
}
}
// 这里返回 end +1 也是可以的
// return end +1;
return start;
}
解题
这一题实际上考的是使用二分法的时候，如果因为 start>end 退出 while 循环 start 指向的是什么，指向的是大于目标值的第一个位置。
其实我们可以大概推理出 当因为 start>end 退出 while 循环的时候，start=end+1