关于二分查找法问题

Question

老师，就是有一个问题，就是如果只传一个查找数组，和需要查找的值，l=0，r = 数组的长度 - 1
老师计算中间值的时候，我发现就会出现偏移问题。因为用老师视频的（r-l)/2 程序出现了死循环了，使用debug方式，我发现mid 总是会偏移1位，之前看过老师别的视频有类似的处理 用 l + （r-l + 1) / 2 就完全可以解决，并且也能快速的找到对应的元素。这个就有点迷糊，到底啥时候需要使用偏移，啥时候不用使用。

Answer 1

liuyubobobo 2024-12-21 01:07:12

你说的“看过老师别的视频”应该是指我的体系课的内容，我在我的算法体系课中详细介绍过这个问题。

简单来说，如果是二分查找某个值，不存在这个问题；

只有在二分查找上界或者下界的时候（大于或者大于等于 v 的最小值；小于或者小于等于 v 的最大值），才可能出现这个问题，因为此时，二分查找可能出现死循环；

一大出现死循环，使用 l + （r-l + 1) / 2 的方式都可以解决。

是否出现死循环不需要运行程序来判断，通过查看在极端情况 l 和 r 是否可能没有变化就可以。只要 l 和 r 可能不动，就会出现死循环。

更具体的在我的体系课程中有详细介绍，课程中有几个同学的问题也和此相关，我做了详细回答，可以参考。

继续加油！：）