您真的会二分查找吗
发布时间： 2012-08-21 13:00:22 作者： rapoo
你真的会二分查找吗？
[cpp]
int?bSearch(int?begin,?int?end,?int?e)??{??????int?mid,?left?=?begin,?right?=?end;??????while(left?<?right)??????{??????????mid?=?(left?+?right)?>>?1;??????????if(num[mid]?>?e)?right?=?mid;??????????else?left?=?mid;??????}??????return?mid;??}???
??????[cpp]
int?bSearch(int?begin,?int?end,?int?e)??{??????int?mid,?left?=?begin,?right?=?end;??????while(left?<=?right)??????{??????????mid?=?(left?+?right)?>>?1;??????????if(num[mid]?>=?e)?right?=?mid?-?1;??????????else?left?=?mid?+?1;??????}??????return?left;??}??对于YES_RIGHT或者NO_LEFT
[cpp]int?bSearch(int?begin,?int?end,?int?e)??{??????int?mid,?left?=?begin,?right?=?end;??????while(left?<=?right)??????{??????????mid?=?(left?+?right)?>>?1;??????????if(num[mid]?>?e)?right?=?mid?-?1;??????????else?left?=?mid?+?1;??????}??????return?right;??}???
??????不做过多说明，单步调试自然会发现执行过程，要说明的是，两个程序都用了right = mid - 1; left = mid +1;用这个的前提是终止条件要是left <= right。要注意的是，有的二分查找不是只需要四种情况中的一种，而是组合使用，比如查找一个数，如果找到则×××不然则×××，如果是YES_LEFT || NO_RIGHT组合或者YES_RIGHT || NO_LEFT组合就直接用上面代码即可，否则就要综合用了，加一些判断等说明，因为用的时候不多，就不给出代码了，自己如果遇到可以试着写写，当成模板，以后直接用～
?????? 现在，是不是觉得二分查找很容易呢？如果总结过的话……