二分查找

发表于 | 分类于 ，

什么是二分查找:

二分查找是一个基础算法. 其过程就是将需要查找的值与中间值进行比较, 每次都将查找的区间缩小一半, 最后得到答案. 时间复杂度为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;