所谓二分查找,就是在有序的数组中查找某一值的元素,基本方法是分治
不保证Key(所查找的关键字)在集合中的查找
例如：最长不下降子序列中的二分查找,当动规到某一位置时,要知道在辅助数组中Key的位置,需要找到Key所在位置或仅比Key小的（c[i]\leqslant key
|
|
inline int bin(int x) { int b=0,e=MAX,k=(b+e+1)>>1; while (b<e) { if (f[k]>x)e=k-1; else if (f[k]<=x)b=k; k=(b+e+1)>>1; } return k; } //关键在于"k=(b+e+1)>>1;" //这条语句能满足一个很好的性质,即b,e如果相邻的话(e-b=1),则k=e而不是b,当然,如果e-b=2的时候,k=(b+e)/2 |
CODE:
|
|
#include <stdio.h> int bins(int key) { static int l,r,y;//l:左界,r,右界 l=0;r=n; while (l<=r){ y=(l+r)>>1;//位运算右移,相当于除2 if (m[y] > key) r=y-1;else if (m[y] < key) {if (m[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便 else return y; } } |
这样写好像很简单
相关
顶一下……