二分查找的变异写法

 

最近接触的二分查找变的多了起来

先推荐一篇很不错的博客叭

https://blog.csdn.net/zxzxzx0119/article/details/82670761

首先二分查找普通的写法就是

int bina(int *a,int key){
    int l = 1;
    int r = n;
    int coun = 0;
    while(l<=r){
        //coun++; printf("%d\n",coun);
        int mid = (l+r)>>1;
        if(a[mid]==key){
            return mid;
        }
        if(a[mid]>=key){
            r = mid-1;
        }
        else{
            l = mid+1;
        }

    }

  
    return -1;
}

这个地方l一定是从开始的下标，r一定是结束的下标

这种写法是比较方便的

但是这种方法的前提是数组递增且不存在重复的元素

所以当存在重复的元素时我们便面临如何选取的问题

这里我简单介绍三种方法，并且进行一个相应的总结相关的写法（也是根据链接博客里面的详细讲解总结的）

首先是找到相同元素最左边的元素

int bina(int *a,int key){
    int l = 1;
    int r = n;
    int coun = 0;
    while(l<=r){
        //coun++; printf("%d\n",coun);
        int mid = (l+r)>>1;
       /* if(a[mid]==key){
            return mid;
        }*/
        if(a[mid]>=key){
            r = mid-1;
        }
        else{
            l = mid+1;
        }

    }

    if(l<=n&&a[l]==key){
        return l;
    }

    return -1;
}

可以看到这里我们把a[mid]==key的判断条件注释掉了

while里面判断的关键在于r=mid-1的>=号 意思是就算找到a[mid]==key区间也要往右缩进直到找到第一个大于等于key的元素

如果这个元素的下标合理（l<=n）且这个元素==key那么就找到了key返回下标 否则返回-1

 

 

 

那么我们可以根据此推出第二种情况 找到第一个>=key的元素

其实上一个我们找到的就是第一个>=key的元素 下面的条件只不过是加了一个特判

所以代码为

int bina(int *a,int key){
    int l = 1;
    int r = n;
    int coun = 0;
    while(l<=r){
        //coun++; printf("%d\n",coun);
        int mid = (l+r)>>1;
       /* if(a[mid]==key){
            return mid;
        }*/
        if(a[mid]>=key){
            r = mid-1;
        }
        else{
            l = mid+1;
        }

    }

    return l;
}

 

 

那么第三种情况是找第一个>key的元素，所以这里我们可以直接把上一个while里面的判断条件改成>key就ok辽

int bina(int *a,int key){
    int l = 1;
    int r = n;
    int coun = 0;
    while(l<=r){
        //coun++; printf("%d\n",coun);
        int mid = (l+r)>>1;
       /* if(a[mid]==key){
            return mid;
        }*/
        if(a[mid]>key){
            r = mid-1;
        }
        else{
            l = mid+1;
        }

    }

    return l;
}

 

那么如果找最后一个或者最右边的话把l和r调换一下就ok了！