Java教程

二分查找的秘密

本文主要是介绍二分查找的秘密，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

left=0 right=length-1时，当进行left和right移动的时候一定要等于二分点+1或二分点-1 （不然，假设终止条件是left>right，当target=arr[lenth-1]的时候会死循环）

left=0 right=length时, 当进行left和right移动的时候就可以等于二分点

why？

如下情况，当right=left+1时，二分点一定是left，而当target=arr[right]时，进入死循环。所以在进行left移动和right移动的时候一定要注意+-1

而让right=length进行初始化可以有效避免这一个问题。因为在初始状态下,不可能有arr[right]=target，而在非初始状态下到达arr[right(也就是上一步的二分点)]=target的前提条件是在上一步比较中arr[二分点]>target，这显然是自相矛盾的。所以这样初始化可以不用在意在移动left和right时是否对二分点+-1。

arr[left]=target根本无需考虑。因为二分点总能落在left上从而顺利结束循环。

这篇关于二分查找的秘密的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航