chapter_searching/binary_search/

[giscus[bot]]

chapter_searching/binary_search/

一本动画图解、能运行、可提问的数据结构与算法入门书

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

[BaibaiCUMT]

请问对于 《旋转数组的最小数字》这种题目，题解使用了双闭区间的初始值，但终止条件却是left<right，在移动right的时候也采用了right = mid 而不是 right = mid - 1，对于这种灵活的条件该怎么学习和使用呢，谢谢。

[krahets]

非常好的问题！旋转数组的最小数字 这道题目的特殊点在于输入数据不是完全有序的，而是被分成了两个有序区间，所以无法简单地套用以上模板来做。这时候只能根据具体分析来写，比如：

• 以上链接中的解题代码，确实是以 “双闭区间” 来定义 i 和 j 的。
• 终止条件也可以是 left <= j ，导致会多循环一次，而且一定是执行 j -= 1 ，因此是多余操作；
• right = mid 则是具体分析得到的结果，由于我们要找的是右子数组的首元素，因此是 left = mid + 1, right = mid ；而如果我们要找的是左子数组的末尾元素，则应改为 left = mid , right = mid - 1 了；本质上是在保证 “安全地缩减区间” 。

其实，除了这道题外，如果输入的有序数组中存在重复值，并且希望找 “第一个” 或 “最后一个” 某元素，那么也需要根据具体情况对代码做一定改动。我觉得还是有必要写一下这个部分，先 Mark 下，后续补上！

[BaibaiCUMT]

非常感谢！！
我对于本例的做法是：首先我使用基本的模板去套这个题，但是对于本例中的 m < j 的情况，我需要结合题目来判断能否排除nums[m]；本例中m<j时，m属于右区间可能是答案，所以不能使用 j = m-1。

[hlf2016]

这个二分查找的代码认真的吗 m := (i + j) / 2 // 计算中点索引 m 如果 i + j 是个奇数的话 咋么办 出现小数位 还能找到吗

[krahets]

Hi, Go 中的除法运算符 / 是向下取整的

[Apple9]

为什么线性查找和哈希查找的内容都没有了？

[krahets]

更新了下目录结构～请见 搜索算法 章

[ghost]

可以用>>1取代/2 精度高一点点

[BoyZhouY]

这里是想说更快吧？

[krahets]

@BoyZhouY 通常也不会更快～请相信编译器的能力，将优化工作交给它。

[wmjim]

我查了一下，是由于 / 2 是向零取整，>> 1是向下取整，如果考虑负奇数， / 2 没有 >>1 描述的更准确。

[CauchyJenson]

@krahets oiwiki是这么写的：参考 编译优化 #位运算代替乘法，对于 n 是有符号数的情况，当你可以保证 $n\ge 0 $时，n >> 1 比 n / 2 指令数更少。

[krahets]

@CauchyJenson 是的，但在平时编码中，还是把优化工作交给编译器吧，我们通常更需要关注的是写出清晰、可读、可维护的代码。

[fallenleavesguy]

不够看啊，动态规划啥时候安排上。感谢K神

[krahets]

最近冲刺一波，争取这个月到下个月哈

[LyntNy4n]

双闭区间在索引是无符号整数的语言中是有坑的
比如Rust 它的索引是usize类型 在nums=[1,2,3] target=0(不存在且比nums[0]小)的情况下 会因为 j = m - 1; 崩溃, 因为j已经等于0了还要-1
而左闭右开区间因为这个情况的语句是j = m; 所以不会有这个问题(但是左闭右开的rust示例代码没改过来)

[XIAOZHUXUEJAVA]

let nums = vec![2, 3, 4, 7, 9];
let target = binary_search(&nums, 1);
println!("{}", target);

就像是这样，测试是不过的；
我之前已经和K提过issue了，可能没有被重视吧，直接close了

[XIAOZHUXUEJAVA]

#479

[krahets]

确实，这个角度看左闭右开是有优势的。从做算法题角度看，建议可以直接使用 i32 ，在索引时转回 usize 。

已被 @night-cruise 于 #479 修复

[wang-yulin]

大佬，问个题外话，你写作用的什么工具啊？

[krahets]

Hi，我用 vscode 或者 typora

[liuyanqing1023]

public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;

while(left <= right) {
  int mid = left + (right - left) / 2;
  
  if(nums[mid] == target) {
    return mid; 
  } else if(nums[mid] < target) {
    left = mid + 1;  
  } else {
    right = mid - 1;
  }
}

return -1; 

}

感觉这样更清晰

[CopyDragon10086]

确实，用左和右确实更清楚明了

[zaipingy]

左闭右开区间的rust算法中，右边界缩小写错了，应该是 j=m; 不是 j=m-1;

[night-cruise]

提了个 pr：#1006

[cuppar]

Rust 代码off-by-one error:

/* 二分查找（左闭右开区间） */
fn binary_search_lcro(nums: &[i32], target: i32) -> i32 {
    // 初始化左闭右开区间 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
    let mut i = 0;
    let mut j = nums.len() as i32;
    // 循环，当搜索区间为空时跳出（当 i = j 时为空）
    while i < j {
        let m = i + (j - i) / 2;      // 计算中点索引 m
        if nums[m as usize] < target {         // 此情况说明 target 在区间 [m+1, j) 中
            i = m + 1;
        } else if nums[m as usize] > target {  // 此情况说明 target 在区间 [i, m) 中
// ###########################################
// #####         shoule be `j = m;`           ##############
// ###########################################
            j = m - 1;
        } else {                      // 找到目标元素，返回其索引
            return m;
        }                       
    }
    // 未找到目标元素，返回 -1
    return -1;
}

[night-cruise]

提了一个 pr 修复了：#1006

[WangBenpeng]

K神，左闭右开区间，输入target = 35; nums = { 1, 3, 6, 8, 12, 15, 23, 26, 31, 35 } 时，应该返回-1才对，结果是返回的9。初始化的时候应该这样才对

        int i = 0, j = nums.length - 1;

/* 二分查找（左闭右开） */
static int binarySearchLCRO(int[] nums, int target) {
        // 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
        int i = 0, j = nums.length - 1;
        // 循环，当搜索区间为空时跳出（当 i = j 时为空）
        while (i < j) {
            int m = i + (j - i) / 2; // 计算中点索引 m
            if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
                i = m + 1;
            else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
                j = m;
            else // 找到目标元素，返回其索引
                return m;
        }
        // 未找到目标元素，返回 -1
        return -1;
    }

还是我对左闭右开区间理解有问题，麻烦解答一下

[krahets]

Hi，就应该返回 9 呀，代表数字 35 在数组的索引 9 处

[WangBenpeng]

左闭右开的话，这个数组是不包含35的，应该返回索引-1才对

[krahets]

这个区间是为了 i, j 的移动定义的，不是为了限制数组内元素而存在的。
换言之，双闭区间和左闭右开区间要完成的目标是完全一样的。建议再理解一下本文内容

[WangBenpeng]

谢谢，理解了，这个双闭区间和左闭右开区间是查找的区间，和传入的nums数组弄混了

[bluebean-cloud]

请问 RUBY 的代码片段是缺失了吗？
如果需要补充的话我可以来提一个PR

[jessie717]

hi, 对应的题目能否帮忙给出力扣相应或相似题目的链接?

[krahets]

Hi，推荐仓库 https://github.com/krahets/LeetCode-Book 的题单，题目分类和本书一致

[jessie717]

谢谢!已跟练!
比自己慢慢找的快多了

[Yerosius]

二分的mid有3种写法：

1. mid=(left+right)/2
2. mid=left+(right-left)/2
3. mid=(left+right)>>1

[Elikke-007]

第三种写法有溢出的可能，可以优化成 left + ((right-left) >> 1)

[jiuerya7]

1和3不是一个意思吗

[linfaimom]

emmm 看到二分我的第一思路居然是直接用递归做了。。。不过这个办法只能返回 true / false，没法记录 idx，尴尬

func binarySearch(sortedArr []int, wantedVal int) bool {
	if len(sortedArr) == 0 || (len(sortedArr) == 1 && sortedArr[0] != wantedVal) {
		return false
	}
	middle := len(sortedArr) / 2
	if wantedVal == sortedArr[middle] {
		return true
	}
	if wantedVal < sortedArr[middle] {
		return binarySearch(sortedArr[:middle], wantedVal)
	}
	if wantedVal > sortedArr[middle] {
		return binarySearch(sortedArr[middle+1:], wantedVal)
	}
	return false
}

[CodeGetters]

为什么不把BFS、DFS拎出来讲呀

[wpeng2005]

请问最后二分查找的局限性当中，如果按照代码的顺序，最少的单元操作数不应该是5个单元吗

[PotatoSmith]

拓宽思路，小数据量情况下，线性查找反而比二分查找更快。不要只看算法的时间复杂度，更要结合实际场景

[akiradavidsong]

更正：图 10-3里的循环终止条件：i>j这里应该是笔误typo了，应该是i<j才对

[sinabs]

没有错误吧, i<j是符合条件还有继续循环的直至i>j循环终止

[jiuerya7]

没有错

[6mmLIU]

妙

[Li9htning-01]

在半开/双开区间情况下，请问为什么左索引与右索引反而要分别减1或者加1呢？考虑左闭右开情况，为什么右索引为size()呢？是为了适应区间无效的条件（left_index >= right_index）吗？

[Elikke-007]

小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量
较小时，线性查找反而比二分查找更快。
想问问根据这个结论，推倒出当 n >= 32 时，适合使用二分查找，正确吗？
我根据不等式 logn * 6 < n 得到的结论。

[xiaozhuge123]

day08