二分查找

发表于 分类于 ，

什么是二分查找:

二分查找是一个基础算法。其过程就是将需要查找的值与中间值进行比较， 每次都将查找的区间缩小一半 , 最后得到答案. 时间复杂度为 O (logn)

下面是最基本的二分查找代码 

1
2
3
4
5
6
7
8
9
10
11
12
int l,r,key;
while(l<=r)
{
    int mid((l+r)/2);
    if(f(mid)==key)
        return mid;
    else if(f(mid)<key)
        l = mid+1;
    else
        r = mid-1;
}
return -1;

二分查找的变种:

做题的时候经常能碰到这样的情况：寻找某个最大值或最小值. 这个时候也能使用二分查找，不过边界处理要困难一些.

— 寻找符合条件的最大值 — 

1
2
3
4
5
6
7
8
9
bool chk(int m); //判断是否合法
int l,r;
while(l<=r)
{
    int mid((l+r)/2);
    if(chk(mid))	l=mid+1; //符合条件时, 可能[mid+1,r]有解
    else	r=mid-1; //不符合条件时, 在[l,mid-1]查找
}
return r;
— 寻找符合条件的最小值 — 
1
2
3
4
5
6
7
8
9
bool chk(int m);
int l,r;
while(l<=r)
{
    int mid((l+r)/2);
    if(chk(mid))	r=mid-1;
    else	l=mid+1;
}
return l;