chapter_searching/binary_search_insertion/

[giscus[bot]]

chapter_searching/binary_search_insertion/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_searching/binary_search_insertion/

[DXShelley]

对于左右指针的把握可谓精彩

[lyl625760]

不错。 稍微扩展下对于可能有重复元素的处理：
当nums[m] == target 时，
如果是找第一个小于target的数， j = m - 1;
如果是找第一个大于target的数， i = m+1；

[krahets]

确实，搜索左（右）边界在下节有讲

[5710xIa]

太神奇了，本来在想，如果二分第一次就命中要找的i，那么[ i , j - 1 ]岂不是直接把i排除在区间外了？
结果最后因为i = j这一步时会再执行一次if nums[m] < target: i = m + 1 ，结果反而找到了正确的i。

[Zhuzhucatty]

“因此二分结束时一定有：i 指向首个大于 target 的元素，j 指向首个小于 target 的元素。易得当数组不包含 target 时，插入索引为为 i 。”
不好意思，但是 i 不是小于 j 嘛？怎么会出现 i 指向一个大于Target、j指向小于Target的数呢？

[Zhuzhucatty]

没事了，不好意思😬

[lewizheng]

为什么i一定在大于等于target的位置

• i只有m中值小于target才会m+1

        if (nums[m] < target) {
            i = m + 1; 

所以只要i小于target，它就会一直m加一，直到位于大于等于target的位置，甚至超出数组（可以推理一下target大于数组全部的数组情况，可以帮助理解）。
同理，j一定指向首个小于target的位置，因为它在m大于和等于的时候都会target-1，所以它会一直减下去。直到小于target。 当然这只是一个大概的理解。

[buynonsense]

对于
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
}
第三个分支也就是 nums[m]=target，是j=m-1，而不是i=m+1。实际上是因为最终用i表示找到的目标，j到i的左边去（而不是i到j的右边去）这是一开始的隐藏条件

[DarkIdiot]

对于最后一段代码，个人感觉还是有点问题，如果说我们传入的数组刚好只有一个元素，不论target为何值，程序要么在无限循环，要么会越界。

[krahets]

测试结果：

数组 nums = [6]
元素 2 的插入点的索引为 0
元素 6 的插入点的索引为 0
元素 20 的插入点的索引为 1

编程是实践学科，强烈建议前往代码仓 https://github.com/krahets/hello-algo 下载源代码，本地运行代码

[cuppar]

这部分Rust代码中挺多off-by-one错误的，还有一些copy-paste错误。

/* 二分查找插入点（存在重复元素） */
pub fn binary_search_insertion(nums: &[i32], target: i32) -> i32 {
    let (mut i, mut j) = (0, nums.len() as i32 - 1);    // 初始化双闭区间 [0, n-1]
    while i <= j {
        let m = i + (j - i) / 2;    // 计算中点索引 m
        if nums[m as usize] < target {
            i = m + 1;  // target 在区间 [m+1, j] 中
        } else if nums[m as usize] > target {
            j = m - 1;  // target 在区间 [i, m-1] 中
        } else {
            j = m - 1;  // 首个小于 target 的元素在区间 [i, m-1] 中
        }
    }
    // 返回插入点 i
    i
}

[cuppar]

/* 二分查找插入点（存在重复元素） */
pub fn binary_search_insertion(nums: &[i32], target: i32) -> i32 {
    let (mut i, mut j) = (0, nums.len() as i32 - 1);    // 初始化双闭区间 [0, n-1]
    while i <= j {
        let m = i + (j - i) / 2;    // 计算中点索引 m
        if nums[m as usize] < target {
            i = m + 1;  // target 在区间 [m+1, j] 中
        } else if nums[m as usize] > target {
            j = m - 1;  // target 在区间 [i, m-1] 中
        } else {
            // ######     should return m;     #################
            j = m - 1;  // 首个小于 target 的元素在区间 [i, m-1] 中
        }
    }
    // 返回插入点 i
    i
}

[night-cruise]

这是因为 nums 数组中存在重复元素，binary_search_insertion 的目的是找到第一个等于 target 的元素的数组下标。

[cuppar]

不是，第一段代码有误，第二段没问题。第一段是无重复元素的

[EndlessCheng]

本节的代码都是“双闭区间”写法。有兴趣的读者可以自行实现“左闭右开”写法。

之前整理了二分的几种写法，除了左闭右闭，还有左闭右开和左开右开，具体见 这期视频。

[AstoraGray]

灵神！

[maxkwok]

存在多个target的情况下，直接插找到的第一个target的左边，结果得到的数组也一样吧，为什么要找最左边的target？

[480284856]

因为这是题目要求

[jessie717]

相关题目: 35. 搜索插入位置

[nfrjyrymccan]

以前看了很多题解, 都不太明白二分插值为什么最后返回的是i, 今天终于明白了!!!

[JackTvT]

10.2.2 中到步骤7 m=i并且nums[m] = target 时是不是就可以直接返回i了，i作为左边界，nums[i] == target时，应该也是最左边的target 了吧，后面再缩小区间就不需要了，不知道是不是这样的？

[tron-robin]

还是要等到j<i才可以跳出的，毕竟i向后跳的时候，可能会跳过某个target

[JackTvT]

您好，我还是不太明白，数组是有序的，只有当nums[m] < target时才会有i = m + 1，i是m后面的一个元素，nums[m] < target 时他后面的一个元素最多也就==target，哪种情况会跳过target呢？

[tron-robin]

您好，我上面的描述是错的。根据我的理解，i<=j是循环执行的条件，也就是说，j<i是循环终止的条件，所以即使找到了最左边的target，还是要再次缩小区间以达到终止循环的目的

[tron-robin]

你好你好，我测试了下，你最开始的描述是正确的。两种代码的运行过程：
1.文中的，借用不断缩小区间达到终止循环的目的
2.你上面的说法，在每次缩小区间前先判断是否满足已找到最左边target的条件，以达到终止循环的目的
两种结果是一样的，看取舍：
一种是多进行一次区间缩小，一种是每次循环判断是否已找到

[JackTvT]

确实，我关注了图10-6的步骤，没有考虑代码，从代码角度看的话确实您的方式更优，多谢解答