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]

灵神！

[lt421]

灵神！

[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的步骤，没有考虑代码，从代码角度看的话确实您的方式更优，多谢解答

[Chr1sdian]

def binary_search_insertion(nums: list[int], target: int) -> int:
"""二分查找插入点（存在重复元素）"""
i, j = 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]
while i <= j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # target 在区间 [m+1, j] 中
elif nums[m] > target:
j = m - 1 # target 在区间 [i, m-1] 中
else:
j = m - 1 # 首个小于 target 的元素在区间 [i, m-1] 中
# 返回插入点 i
return i
k佬，最后else的注释是不是有点小问题，我觉得应该是[m-1,i]吧，毕竟迭代到最后j=m-1

[MambaFly]

1、最左
1.1 如果需要找到某个元素的最左插入点，那么在target==nums[m]时 可以写成else: j = m - 1（尽量往左移动）
并且return i
1.2 如果是要找到某一重复元素的最左边元素（前提是已存在），
也是return i；而此时 j 恰好== i-1

2、最右
2.1 如果需要找到某个元素的最右插入点，那么在target==nums[m]时 可以写成else: i = m + 1（尽量往右移动）
并且return i
2.2 如果是要找到某一重复元素的最右边元素（前提是已存在），
则return j；而此时i == j+1

所以为了统一代码，最好还是想成插入点的下标，这样就都是return i，而根据最左或最右来调整else条件

[jerry609]

没有kmp算法吗

[HsCodeLab]

K神,我在想一种可能性,以上只提供了数组中存在6的步骤图,能否也提供一下不存在的步骤图.甚至进一步,读者选择一个数,跟据生成对应的搜索步骤图,而不是固定的只有提前写好的几个步骤图.我可以自己写代码研究一下,但是前提是要知道算法的执行步骤,所以在学习的时候不能结合得很好,所以K神,能搞一下吗?

[HsCodeLab]

或者哪位老哥来搞一下这本书算法步骤的图形化?

[Than-Sing]

NOTE：指针i在向大于等于target的元素靠近，指针j始终在向小于等于target的元素靠近。所以二分结束时一定有：i指向首个大于target的元素，j指向首个小于target的元素。

解释得太好了！豁然开朗

[Than-Sing]

NOTE：补充，在区分有无重复元素时，就考虑i == j == m这种情况，思考应该i还是j移动即可

[twx0504]

嗨大家 我是刚学习算法的小白。我想实现了一个可以既可以查找最左target的索引，又可以查找最右target的索引的函数。希望大家可以帮我检查逻辑错误之类的，还是有更好的实现方式也可以分享。谢谢

function binarySearchInsertion(arr, target, isRightInsertion = false) {
  let i = 0;
  let j = arr.length - 1;
  while (i <= j) {
    let m = Math.floor(i + (j - i) / 2);
    if (arr[m] < target) i = m + 1;
    else if (arr[m] > target) j = m - 1;
    else {
      if (!isRightInsertion) {
        j = m - 1; // target is found, but there might be more target to the right of target.
      } else {
        i = m + 1; // target is found, but there might be more target to the left of target.
      }
    }
  }
  return i;
}