第七次课-二分查找

左边界二分查找

模板(化简)

for(int i=1;i<=n;i++)
{
    int l=1-1,r=n+1,ans=-1;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(a[mid]<x)
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
        if(a[r]==x)
        {
            cout<<r<<" ";
        }
        else
        {
            cout<<"-1"<<" ";
        }
    }
}

原理

1.for循环：查找每一个数字，所以是从1至n

2.l,r,ans的初始值：为了能让x为最小的值或最大的值时仍能进入while循环，就把l设为0，r设为n+1,ans就是最终的下标

3.while循环：为了不进入死循环，就写为l+1<r

4.mid的初始值：在l与r之间找，为了能最快，最保险，就在二者中间找

4.两个if个判断：当a[mid]要小于x时，说明x在a[mid]的右边，所以将l定为mid，其余就将r定在mid是因为只有在l<mid时才会移动，所以l与r其实是相差越来越小，所以最终l是第一个x前一个数字的下标，r就是第一个x

右边界二分查找

模板(化简)

for(int i=1;i<=n;i++)
{
    int l=1-1,r=n+1,ans=-1;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(a[mid]>x)
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
        if(a[l]==x)
        {
            cout<<l<<" ";
        }
        else
        {
            cout<<"-1"<<" ";
        }
    }
}

原理

1.for循环：查找每一个数字，所以是从1至n

2.l,r,ans的初始值：为了能让x为最小的值或最大的值时仍能进入while循环，就把l设为0，r设为n+1,ans就是最终的下标

3.while循环：为了不进入死循环，就写为l+1<r

4.mid的初始值：在l与r之间找，为了能最快，最保险，就在二者中间找

4.两个if个判断：当a[mid]要大于x时，说明x在a[mid]的左边，所以将r定为mid，其余就将l定在mid是因为只有在r>mid时才会移动，所以l与r其实是相差越来越小，所以最终r是最后一个x的后一个数的下标，l就是最后一个x的下标