如何写出正确的二分查找

1、如何写出正确的二分查找？利用循环不变式理解二分查找及其变体的正确性以及构造方式序言本文以经典的二分查找为例，介绍如何使用循环不变式来理解算法并利用循环不变式在原始算法的基础上根据需要产生算法的变体。谨以本文献给在理解算法思路时没有头绪而又不甘心于死记硬背的人。二分查找究竟有多重要？编程之美第2.16节的最长递增子序列算法，如果想实现O(n2)到O(nlogn)的时间复杂度下降，必须借助于二分算法的变形。其实很多算法都是这样，如果出现了在有序序列中元素的查找，使用二分查找总能提升原先使用线性查找的算法。然而，虽然很多人觉得二分查找简单，但随手写一写却不能得到正确的结果：死循环、边界条件等等问题伴

2、随着出现。编程珠玑第四章提到：提供充足的时间，仅有约10%的专业程序员能够完成一个正确的二分查找。当然，正确的二分查找和变体在算法书籍以及网络上随处可得，但是如果不加以理解，如何掌握？理解时，又往往因想不清楚，一知半解，效果有限。我在看相关的变体算法时就觉得一片茫然，不得要领：或许这个算法可以这么写，稍微变下要求就不能这么写了；举正例说明算法在某些情况下可以正常工作、举反例说明算法有错误固然可行，但仅有例子是不够的，怎样一劳永逸地证明自己几经修改的算法之正确？如果每一个变体都进行孤立地理解，那么太花费时间，而且效果也不好。如何解决这个问题？在思考方法和查阅书籍之后发现，还是要靠循环不变式来完成

3、算法正确性的理论支撑。或许你曾了解过循环不变式，但如果不使用的话，是看不到它的强大之处的：不仅仅能帮助你证明算法正确性，同时也帮助你理解算法，甚至能帮助你在基本算法的基础上，构造出符合要求的相应算法变体。这些都将在后文的各个算法说明中看到。知识准备结合算法导论和编程珠玑，下面说明循环不变式的概念与性质。循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法，它是一个需要保证正确断言。对于循环不变式，必须证明它的三个性质：初始化：它在循环的第一轮迭代开始之前，应该是正确的。保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。终止：循环能够终止，

4、并且可以得到期望的结果。文章说明(1)在推导每次数组减少的长度时，mid是不能代换成(left+right)/2的。这种形式代表了非整型的运算，没有舍去小数部分，而在代码中实际的mid是会舍去小数部分的。(2)代码部分的=和=意义同C语言；文字说明部分的=代表赋值，=代表等式推导或者逻辑判断，由上下文而定。(3)除了3和5外，最初的各个变体代码参考于：二分查找，你真的会吗？为了符合思路的前后连贯和说明循环不变式，做了一些修改。原文的测试很方便，读者可以自行参考。(4)根据getgoing的提示和对原始参考代码的回顾，mid = (left+right)/2本身可能导致溢出，比较保险的写法是mi

5、d = left + (right-left)/2，如果想通过移位而不是除法提升速度，可以写成mid = left + (right-left)1)。 本文最初版本没有注意到这一点，现在已经修改，这个表达式和最初的比不是很直观，专门在这里说明。当然，在理论推导而不是程序运行时是不必考虑溢出的，mid = (left+right)/2和mid = left + (right-left)/2总是相等，因此(1)和全文中的推导并未对此修改。1.二分查找值为key的下标，如果不存在返回-1。循环不变式：如果key存在于原始数组0,n-1，那么它一定在left,right中。初始化：第一轮循环开始之前，

6、处理的数组就是原始数组，这时显然成立。保持：每次循环开始前，key存在于待处理数组arrayleft, ., right中。对于arraymidkey，arraymid, ., right均大于key，key只可能存在于arrayleft,.,mid-1中；对于arraymid=key，查找到了key对应的下标，直接返回。在前两种情况中，数组长度每次至少减少1（实际减少的长度分别是mid-left+1和right-mid+1），直到由1（left=right）变为0（leftright），不会发生死循环。终止：结束时，leftright，待处理数组为空，表示key不存在于所有步骤的待处理数组，

7、再结合每一步排除的部分数组中也不可能有key，因此key不存在于原数组。cppview plaincopy1. intbinsearch(int*array,intlength,intkey)2. 3. if(!array)4. return-1;5. intleft=0,right=length,mid;6. while(left=right)7. 8. mid=left+(right-left)/2;9. if(arraymidkey)13. 14. right=mid-1;15. else16. returnmid;17. 18. return-1;19. 2.二分查找返回key(可能有

8、重复)第一次出现的下标x，如果不存在返回-1循环不变式：如果key存在于数组，那么key第一次出现的下标x一定在left,right中，且有arrayleft=key。初始化：第一轮循环开始之前，处理的数组是0,n-1，这时显然成立。保持：每次循环开始前，如果key存在于原数组，那么x存在于待处理数组arrayleft, ., right中。对于arraymid=key, arraymid是arraymid, ., right中第一个大于等于key的元素，后续的等于key的元素（如果有）不可能对应于下标x，舍去。此时x在left, ., mid之中。数组减少的长度为right-(mid+1)+

9、1，即right-mid，根据while的条件，当right=mid时为0。此时right=left，循环结束。终止：此时left=right。在每次循环结束时，left总是x的第一个可能下标，arrayright总是第一个等于key或者大于key的元素。那么对应于left=right的情况，检查arrayleft即可获得key是否存在，若存在则下标为x；对于leftright的情况，其实是不用考虑的。因为left=上一次循环的mid+1，而midright，意味着mid = right，但此时必有left = right，这一轮循环从开始就不可能进入。cppview plaincopy1.

10、intbinsearch_first(int*array,intlength,intkey)2. 3. if(!array)4. return-1;5. intleft=0,right=length-1,mid;6. while(leftright)7. 8. mid=left+(right-left)/2;9. if(arraymidkey)10. left=mid+1;11. else12. right=mid;13. 14. if(arrayleft=key)15. returnleft;16. return-1;17. 3.二分查找返回key(可能有重复)最后一次出现的下标x，如果不存

11、在返回-1（模仿2的第一版）循环不变式：如果key存在于数组，那么key最后一次出现的下标x一定在left,right中，且有arrayleft=key。初始化：第一轮循环开始之前，处理的数组是0,n-1，这时显然成立。保持：每次循环开始前，如果key存在于原数组，那么x存在于待处理数组arrayleft, ., right中。对于arraymidkey, arraymid, ., right均大于key，x只可能在left, ., mid-1之中。数组减少的长度为(right-mid)+1，同样至少为1。终止：此时left=right,right总是从数组末尾向开始的倒序中第一个候选的x，检

12、查它的值是否符合要求即可。而left总是上一轮删掉失去x资格的元素后的第一个元素，不过这里用不到。说明：与上一种不同，这个算法不能简单地根据对称，从上一个算法直接改过来，由于整数除法总是舍弃小数，mid有时会离left更近一些。所以这种算法只是沿着上一个算法思路的改进，看上去并不是很漂亮。cppview plaincopy1. intbinsearch_last(int*array,intlength,intkey)2. 3. if(!array)4. return-1;5. intleft=0,right=length,mid;6. while(leftkey)10. right=mid-1

13、;11. elseif(arraymid=key)12. if(left=mid)13. if(arrayright=key)14. returnright;15. else16. returnleft;17. else18. left=mid;19. else20. left=mid+1;21. 22. 23. if(arrayright=key)24. returnright;25. return-1;26. 4.二分查找返回key(可能有重复)最后一次出现的下标x，如果不存在返回-1（修改版）根据3中的讨论，可以发现不能直接照搬的原因是mid=(left+right)/2的舍弃小数，在l

14、eft+1=right且arrayleft=key时，如果不加以人为干预会导致死循环。既然最终需要干预，干脆把需要干预的时机设置为终止条件就行了。使用while(leftright-1)可以保证每次循环时数组长度都会至少减一，终止时数组长度可能为2(left+1=right)、1(left=mid，上一次循环时right取mid=left)，但是不可能为0。(每一次循环前总有left=midright)。同3一样，right总是指向数组中候选的最后一个可能为key的下标，此时只需先检查right后检查left是否为key就能确定x的位置。这样就说明了循环不变式的保持和终止，就不再形式化地写下来

15、了。对于两种情况的合并：arraymid = key时，mid有可能是x，不能将其排除；arraymidkey时，如果让left = mid+1，不会违反循环不变式的条件。但是由上面的讨论可知，将left=mid也是可以的，在达到终止条件前能保证数组长度单调减少。因此把两种情况合并成最终形式。cppview plaincopy1. intbinsearch_last_v2(int*array,intlength,intkey)2. 3. if(!array)return-1;4. intleft=0,right=length-1,mid;5. while(leftright-1)6. 7. m

16、id=left+(right-left)/2;8. if(arraymid=left，违反则意味着x不存在。写下arraymid的比较判断分支：(1) arraymidkey, 意味着x只可能在arraymid, ., right之间，下一次循环令left = mid，数组长度减少了(mid-1)-left+1 = mid-left，这个长度减少量只有在right-left=key，意味着x只可能在arrayleft ,. ,mid-1之间，下一次循环令right = mid-1，同样推导出数组长度至少减少了1。这样，把循环条件缩小为rightleft+1，和4一样，保证了(1)中每次循环必然

17、使数组长度减少，而且终止时也和4的情况类似：终止时待处理数组长度只能为2或1或者空（leftright）。终止：接着保持中的讨论，结束时，符合的x要么在最终的数组中，要么既不在最终的数组中也不在原始的数组中（因为每一次循环都是剔除不符合要求的下标）。数组长度为2时，right=left+1，此时先检查right后检查left。如果都不符合其值小于key，那么返回-1。数组长度为1时，只用检查一次；数组长度为0时，这两个都是无效的，检查时仍然不符合条件。把这三种情况综合起来，可以写出通用的检查代码。反过来，根据精简的代码来理解这三种情况比正向地先给出直观方法再精简要难一些。cppview pla

18、incopy1. intbinsearch_last_less(int*array,intlength,intkey)2. 3. if(!array)4. return-1;5. intleft=0,right=length,mid;6. while(leftright-1)7. 8. mid=left+(right-left)/2;9. if(arraymidkey)10. left=mid;11. else12. right=mid-1;13. 14. if(arrayrightkey)15. returnright;16. elseif(arrayleft=left，违反则意味着x不存在

19、。写下arraymid的比较判断分支：(1) arraymidkey，意味着x只可能在arrayleft ,. ,mid之间，下一次循环令right = mid，数组长度减少了right-(mid+1)+1= right-mid，只有在right=mid时为0，此时left=right=mid。因此，循环条件必须由right=left收缩为rightleft才能避免left=right时前者会进入的死循环。终止：由循环的终止条件，此时left=right。类似2的分析，leftright是不可能的，只有left=right。此时检查arrayrightkey成立否就可以下结论了，它是唯一的候选元素。补充说明：如果是对数组进行动态维护，返回值-1可以改为length+1，表示下一个需要填入元素的位置。cppview plaincopy1. intbinsearch_first_more(int*array,intlength,intkey)2. 3. if(!array)4. return-1;5. intleft=0,right=length-1,mid;6. while(leftright)7. 8. mid=left+