首页 > 代码库 > 二分的姿势=_=

二分的姿势=_=

二分查找:


1:大于等于xx的第一个数

int bin_s(int xx)
{
        int l=1,r=10;
        int ans=-1;
        while(l<=r){
                int m=(l+r)>>1;
                if(a[m]>=xx) ans=m,r=m-1;  //!!!
                else l=m+1;
        }
        return ans;
}
e.g:  int a[]={0,1,2,5,5,5,5,7,8,9,10};
in:           5
out:        3
2:大于xx的第一个数
int bin_s(int xx)
{
        int l=1,r=10;
        int ans=-1;
        while(l<=r){
                int m=(l+r)>>1;
                if(a[m]>xx) ans=m,r=m-1;  //!!!
                else l=m+1;
        }
        return ans;
}
e.g:  int a[]={0,1,2,5,5,5,5,7,8,9,10};
<pre name="code" class="cpp">in:           5
out:        7

3:小于等于xx的第一个数(接近xx)
int bin_s(int xx)
{
        int l=1,r=10;
        int ans=-1;
        while(l<=r){
                int m=(l+r)>>1;
                if(a[m]>xx) r=m-1;
                else ans=m,l=m+1;
        }
        return ans;
}

e.g:  int a[]={0,1,2,5,5,5,5,7,8,9,10};
<pre name="code" class="cpp">in:           5
out:        6
4:小于xx的第一个数(接近xx)
int bin_s(int xx)
{
        int l=1,r=10;
        int ans=-1;
        while(l<=r){
                int m=(l+r)>>1;
                if(a[m]>=xx) r=m-1;
                else ans=m,l=m+1;
        }
        return ans;
}
e.g:  int a[]={0,1,2,5,5,5,5,7,8,9,10};
<pre name="code" class="cpp">in:           5
out:        2



二分的姿势=_=