所谓二分查找,就是在有序的数组中查找某一值的元素,基本方法是分治
不保证Key(所查找的关键字)在集合中的查找
例如：最长不下降子序列中的二分查找,当动规到某一位置时,要知道在辅助数组中Key的位置,需要找到Key所在位置或仅比Key小的（\(\)c[i]\leqslant key
CODE:
这样写好像很简单
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
1
2
3
4
5
6
7
8
9
10
11
#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;
}
}