chapter_searching/binary_search_insertion/ #672
Replies: 20 comments 15 replies
-
对于左右指针的把握可谓精彩 |
Beta Was this translation helpful? Give feedback.
-
不错。 稍微扩展下对于可能有重复元素的处理: |
Beta Was this translation helpful? Give feedback.
-
太神奇了,本来在想,如果二分第一次就命中要找的 |
Beta Was this translation helpful? Give feedback.
-
“因此二分结束时一定有:i 指向首个大于 target 的元素,j 指向首个小于 target 的元素。易得当数组不包含 target 时,插入索引为为 i 。” |
Beta Was this translation helpful? Give feedback.
-
为什么i一定在大于等于target的位置
所以只要i小于target,它就会一直m加一,直到位于大于等于target的位置,甚至超出数组(可以推理一下target大于数组全部的数组情况,可以帮助理解)。 |
Beta Was this translation helpful? Give feedback.
-
对于 |
Beta Was this translation helpful? Give feedback.
-
对于最后一段代码,个人感觉还是有点问题,如果说我们传入的数组刚好只有一个元素,不论target为何值,程序要么在无限循环,要么会越界。 |
Beta Was this translation helpful? Give feedback.
-
这部分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
} |
Beta Was this translation helpful? Give feedback.
-
之前整理了二分的几种写法,除了左闭右闭,还有左闭右开和左开右开,具体见 这期视频。 |
Beta Was this translation helpful? Give feedback.
-
存在多个target的情况下,直接插找到的第一个target的左边,结果得到的数组也一样吧,为什么要找最左边的target? |
Beta Was this translation helpful? Give feedback.
-
相关题目: 35. 搜索插入位置 |
Beta Was this translation helpful? Give feedback.
-
以前看了很多题解, 都不太明白二分插值为什么最后返回的是i, 今天终于明白了!!! |
Beta Was this translation helpful? Give feedback.
-
10.2.2 中到步骤7 m=i并且nums[m] = target 时是不是就可以直接返回i了,i作为左边界,nums[i] == target时,应该也是最左边的target 了吧,后面再缩小区间就不需要了,不知道是不是这样的? |
Beta Was this translation helpful? Give feedback.
-
def binary_search_insertion(nums: list[int], target: int) -> int: |
Beta Was this translation helpful? Give feedback.
-
1、最左 2、最右 所以为了统一代码,最好还是想成插入点的下标,这样就都是return i,而根据最左或最右来调整else条件 |
Beta Was this translation helpful? Give feedback.
-
没有kmp算法吗 |
Beta Was this translation helpful? Give feedback.
-
K神,我在想一种可能性,以上只提供了数组中存在6的步骤图,能否也提供一下不存在的步骤图.甚至进一步,读者选择一个数,跟据生成对应的搜索步骤图,而不是固定的只有提前写好的几个步骤图.我可以自己写代码研究一下,但是前提是要知道算法的执行步骤,所以在学习的时候不能结合得很好,所以K神,能搞一下吗? |
Beta Was this translation helpful? Give feedback.
-
NOTE:指针 解释得太好了!豁然开朗 |
Beta Was this translation helpful? Give feedback.
-
NOTE:补充,在区分有无重复元素时,就考虑 |
Beta Was this translation helpful? Give feedback.
-
嗨大家 我是刚学习算法的小白。我想实现了一个可以既可以查找最左target的索引,又可以查找最右target的索引的函数。希望大家可以帮我检查逻辑错误之类的,还是有更好的实现方式也可以分享。谢谢
|
Beta Was this translation helpful? Give feedback.
-
chapter_searching/binary_search_insertion/
动画图解、一键运行的数据结构与算法教程
https://www.hello-algo.com/chapter_searching/binary_search_insertion/
Beta Was this translation helpful? Give feedback.
All reactions