二分查找

 1 int bin_search(ElementType a[], int num,ElementType obj)
 2 {
 3     int low=0,high=num-1,mid;
 4     while(low<=high)
 5     {
 6         mid=(low+high)/2;
 7         if(a[mid]==obj)
 8         {
 9             return mid;
10         }
11         else if(a[mid]<obj)
12         {
13             low=mid+1;
14         }
15         else
16         {
17             high=mid-1;
18         }
19     }
20     return -1;
21 }

改进一下，更普适点

int bin_search(ElementType a[], int left,int right,ElementType obj)
{
    int low=left,high=right,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(a[mid]==obj)
        {
            return mid;
        }
        else if(a[mid]<obj)
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    return -1;
}

还有一个可能错误的地方需要指出

如果数据量比较大，超过int所能表示的范围，int的范围是0~2^32-1 数据量大于这个范围的话，这其中mid的计算

low+high可能会溢出（待查数据在后半部分），第一个函数同样也面临这样的问题

故而将 mid=（low+high）/2 替换为 mid = low + (high-low)/2

如果含有重复值呢？这两个函数都只能找到其中的一个，任何一个都有可能

题目需要的是出现的第一个值，或最后一个值，或第一个大于该值的值

简单的方法就是拿到下标后，往前或者往后判断一下即可

问题解决了，但就事论事，能不能修改一下函数的逻辑，直接解决问题呢

int bin_search(ElementType a[], int left,int right,ElementType obj)
{
    int low=left,high=right,mid;
    while(low<high)
    {
        mid=low+(high-low)/2;
        if(a[mid]>=obj)
        {
            high=mid;
        }
        else
        {
            low=mid+1;
        }
    }
    return low;
}

稍作修改，该函数返回的下标应该理解为，查找的值应该处于的位置，low的值区间为 [0,n] n为元素的个数，即这个数可能位于最后一个元素的后一个位置

拿到下标后应该判断一下该元素是否是查找的值

至于查找第一个大于该值的位置，可以利用上面这个函数，对于值x，查找的时候填x+1

或者只需要修改一下条件，将>=改为>即可

int bin_search(ElementType a[], int left,int right,ElementType obj)
{
    int low=left,high=right,mid;
    while(low<high)
    {
        mid=low+(high-low)/2;
        if(a[mid]>obj)
        {
            high=mid;
        }
        else
        {
            low=mid+1;
        }
    }
    return low;
}

algorithm中有

lower_bound()

upper_bound()

两个函数的用法参考这篇文章

原文链接: https://www.cnblogs.com/lxzbky/p/12485845.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/400063

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

相关推荐