二分查找插入点
给定一个长度为 n 的有序数组
nums和一个元素target，数组不存在重复元素。现将target插入数组nums中，并保持其有序性。若数组中已存在元素target，则插入到其左方。请返回插入后target在数组中的索引
无重复元素的情况
- 当数组中包含target时，因为题目要求插入到target的左方，所以说插入点的索引就是target的索引
- 当数组中不包含target时，此时我们就需要深入二分的原理刨析
- 当
nums[mid] < target时 l 移动，这意味着指针 l 在向大于等于target的元素靠近。同理，指针 r 始终在向小于等于target的元素靠近- 因此二分结束时一定有：i 指向首个大于
target的元素，j 指向首个小于target的元素- 所以插入索引为 i
有重复元素情况
- 整体流程保持不变，每轮先计算中点索引 mid ，再判断
target和nums[mid]的大小关系，分为以下几种情况- 当
nums[mid] < target或nums[mid] > target时，说明还没有找到target，因此采用普通二分查找的缩小区间操作，从而使指针 l 和 r 向target靠近。- 当
nums[m] == target时，说明小于target的元素在区间 [i,mid−1] 中，因此采用 r=mid−1 来缩小区间，从而使指针 r 向小于target的元素靠近
总的来看，二分查找无非就是给指针 l 和 r 分别设定搜索目标，目标可能是一个具体的元素（例如 target ），也可能是一个元素范围（例如小于 target 的元素）。
在不断的循环二分中，指针 l 和 r 都逐渐逼近预先设定的目标。最终，它们或是成功找到答案，或是越过边界后停止。
原文地址：https://blog.csdn.net/qq_60749185/article/details/136354892
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！