扬中网站建设策划网站设计公司建设网站
🌻算法，不如说它是一种思考方式🍀
算法专栏： 👉🏻123
一、🌱35. 搜索插入位置
- 题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。 - 来源：力扣（LeetCode）
- 难度：简单
- 提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104
🌴解题
这个题要求O(log n) 的算法，且就描述来看也是一个二分法的模子，也不用去考虑暴力搜索了。
二分法
不同的地方在于没有目标元素的时候要求返回一个插入的位置。那是不是在判断left<=right不成立的时候插入，而最后的时刻可能是left右移也可能是right左移导致搜索结束：
最后时刻left右移表示target大于【middle】，应该插入的就是middle右边，刚好此时left右移到该位置；
最后时刻right左移，表示target小于【middle】，应该插入的就是middle左边，而这是也正式left所指位置；
所以不管最后是哪一个操作，最后插入的位置都是left。
例如：
例如：
- code
int middle ;int left=0,right= nums.length-1;while(left<=right){middle=left+(right-left)/2;if(target==nums[middle])return middle;else if(target<nums[middle]){right=middle-1;}else{left=middle+1;}}return left;
本题只需要在搜索结束未命中的时候考虑在哪个位置插入。
☕物有本末，事有终始，知所先后。🍭
🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓
