2、折半查找——查找算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2、折半查找——查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1213字，纯文字阅读大概需要2分钟。

内容图文

2019/11/02

 

2、折半查找   （ 折半查找效率比顺序查找效率高 ,但折半查找只适用于   有序表  ,且限于 有序结构）

要求：

1.线性表必须采用 顺序存储结构。

2.表中元素按关键字有序排列。

算法描述： [时间复杂度：O(log₂n) ]

int Search_Bin(SSTable ST, KeyTable key){

    int low = 1,mid;

    int high = ST.length;

    while(low<=high){

        mid = (low+high) / 2;

        if(key==ST.R[mid].key)  return mid;   //找到待查元素

        else if(key<ST.R[mid].key) high=mid-1; //继续在前一子表进行查找

        else low=mid+1;//继续在后一子表进行查找

    }

    return 0;  //表中不存在待查元素

}

 

折半查找递归算法：

int Search_bin(SSTable ST, KeyType key, int low_in, int high_in){

    int low = low_in;

    int high = high_in;

    int mid=mid = (low+high) / 2; 

    while(low<=high){

        if(key==ST.R[mid].key)  return mid;  //找到待查元素

        else if(key<ST.R[mid].key)  return Search_bin(ST,key,low,mid-1);  //继续在前一子表进行查找

        else return Search_bin(ST,key,low,mid+1);  //继续在前一子表进行查找

    }

    return 0;  //表中不存在待查元素

}

注意：循环执行条件是 low<=high ，而不是  low<high   ，

因为low=high时，查找区间还有最后一个结点，还要进一步比较。

 

折半查找平均查找长度：[ (n+1)/n ]   * [ log₂(n+1)-1 ]

 

内容总结

以上是互联网集市为您收集整理的2、折半查找——查找算法全部内容，希望文章能够帮你解决2、折半查找——查找算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---