算法浅谈——人人皆知却很多人写不对的二分法( 二 ) _二分法

第一种a[mid] = v，很简单，mid就是我们要查找的结果，直接返回。

第二种a[mid] < v，说明我们应该取右边的区间，由于l的位置可以取到，而mid已经不是答案了，所以l = mid + 1 。

第三种a[mid] > v，应该取左边的区间，mid不是答案，但是由于r指向的位置本身就不在候选区间里，所以r = mid，而不是mid-1，因为mid-1可能是答案，而r处的位置是取不到的。
到这里，似乎一切完美，我们可以很顺利地写出代码了。但是还没有结束，依然还有一个小问题。

文章插图

前文说了，a[mid]和v的关系有三种，当a[mid] = v的时候，我们就找到了答案。从这个角度来看，我们二分的时候，通过l和r缩小区间的范围，通过mid来寻找答案。但是既然我们已经折半区间的大小了，那么当区间长度为1的时候，剩下的就是答案，我们为什么还需要通过mid去查找答案呢？如果我们就想通过区间本身来查找答案，那么应该怎么办呢？

也不难，我们需要把a[mid]小于和等于v的两种情况合并，由于a[mid]可能等于v，所以我们不能跳过mid这个位置，l = mid + 1 应该写成l = mid，于是整个代码也就出来了：

defbinary_search(a,v):l,r=0,len(a)whilel+1<r:m=(l+r)/2ifa[m]<=v:l=melse:r=m//通过a[l]==v判断v不存在与a数组当中的情况returnl

4

可能会有同学好奇，如果我不使用左闭右开，而使用闭区间呢，代码又该怎么写？
其实只要把区间想清楚了，写出来也不难。
defbinary_search(a,v):l,r=0,len(a)-1whilel<=r:m=(l+r)/2ifa[m]==v:returnmifa[m]<v:l=m+1else:r=m-1//表示不存return-1不过还有一个小问题，为什么闭区间形式的二分法的判断推荐是while (l <= r)呢？换成while (l < r)行不行？这个问题就留给大家思考。

二分法虽然简单，但这些细节都理解清楚也并不容易，在算法领域当中，如果细节没有理解到位，阴沟里翻船是非常平常的事情。希望今天的文章能对大家有所帮助。