关于二分查找法问题
来源：3-1 从二分查找法看如何写出正确的程序
qq_慕莱坞4316410
2024-12-04
老师，就是有一个问题，就是如果只传一个查找数组，和需要查找的值，l=0，r = 数组的长度 - 1
老师计算中间值的时候，我发现就会出现偏移问题。因为用老师视频的（r-l)/2 程序出现了死循环了，使用debug方式，我发现mid 总是会偏移1位，之前看过老师别的视频有类似的处理 用 l + （r-l + 1) / 2 就完全可以解决，并且也能快速的找到对应的元素。这个就有点迷糊，到底啥时候需要使用偏移，啥时候不用使用。
写回答
1回答
-
liuyubobobo
2024-12-21
你说的“看过老师别的视频”应该是指我的体系课的内容，我在我的算法体系课中详细介绍过这个问题。
简单来说，如果是二分查找某个值，不存在这个问题；
只有在二分查找上界或者下界的时候（大于或者大于等于 v 的最小值；小于或者小于等于 v 的最大值），才可能出现这个问题，因为此时，二分查找可能出现死循环；
一大出现死循环，使用 l + （r-l + 1) / 2 的方式都可以解决。
是否出现死循环不需要运行程序来判断，通过查看在极端情况 l 和 r 是否可能没有变化就可以。只要 l 和 r 可能不动，就会出现死循环。
更具体的在我的体系课程中有详细介绍，课程中有几个同学的问题也和此相关，我做了详细回答，可以参考。
继续加油！：）
00
相似问题