1.lower_bound

　　查找序列中满足a[i]>=k的i的最小值。

　　即——将k插入到i位置上，保证仍然满足序列升序，i最小。

　　假如k比所有都小，则i=1，否则返回n+1

　　

int *Lower_bound(int *l,int *r,int k){    //[l,r)为答案区间    //返回满足*point<=k的最小point    //假如都比k大，则返回l，假如都比k小，返回r-1    while(l + 2 < r)//即l+1
     
      = k)        {            r = mid+1;//mid最小时，r=l+2，可以退出        }else        {            l = mid;//mid最小时，也依然可以增加一位        }    }    //最后的答案区间为l,l+1    if (*l >=k)        return l;    else        return l+1;}
     

 

　　

可以看得到，实现的不怎么优美，但至少健壮性还可以。

 

2.二分答案。

　　假如有一个序列，满足——对于a[i]满足函数C(a[i])，当a[k]<=a[i]时（或者a[k]>=a[i]时），就一定有a[k]也满足函数。

　　对于有这样性质的序列，我们可以进行排序之后二分。

　　假设对于a[k]<=a[i]的满足：

 

　　

l = 1r = n + 1while(l+2
     
      >1;    if (C(mid))    {        //答案在mid左侧都满足，说明真正ans在mid右侧（含mid）        l = mid    }else    {        //不满足，说明ans在mid左侧（不含mid）        r = mid    }}if (C(l)){    return l;}else{    return l+1;}
     

 

 

3.实战：

　　http://www.cnblogs.com/dandi/p/3972213.html ——poj 1064

　　http://www.cnblogs.com/dandi/p/4063473.html ——poj 2456

　　http://www.cnblogs.com/dandi/p/4063525.html ——poj 3258

　　http://www.cnblogs.com/dandi/p/4063554.html ——poj 3273

 　  http://www.cnblogs.com/dandi/p/4067218.html ——poj 3104

　　http://www.cnblogs.com/dandi/p/4068787.html ——poj 3045

　　http://www.cnblogs.com/dandi/p/4075343.html ——poj 3579

　　http://www.cnblogs.com/dandi/p/4077344.html ——poj 3685