点击联系发帖人
时间：2022-06-03 08:22
已经好长时间没有写算法了，今天就写了一个简单的折半查找的算法，很简单。来瞧瞧吧！好了，现在就开始吧！
所谓折半查找，哦，对了，以前的那篇折半排序博文，如果大家看过的话，折半查找那是小 case 了！当然不在话下了。
何为折半查找，就是查找一个数是否在一个给定的排好序的序列中。每次从序列的中间开始比较，如果，中间的数要比你要查找的数字大，那就忽略中间以右的那一部分（当然，我的前提是，序列是升序排列的），就在左部分查找你要查找的值，如果找到了，恭喜你，否则，抱歉，没有找到。就是这个思想，很简单。好了，贴出我的代码，代码才能说明问题，是吧！
说明：也称折半查找，元素必须是有序的，如果是无序的则要先进行排序操作。
基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
C++实现源码（普通版本）：
C++实现源码（递归版本）：
//二分查找--递归实现
一、单项选择题（每小题3分，共30分）
1、在有n 个叶子结点的哈夫曼树中，其结点总数为（）。
2、下列序列中，（）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。
3、若线性表最常用的操作是存取第i 个元素及其前驱的值，则采用（）存储方式节省时间。
4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）。
5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。
7、快速排序算法在最好情况下的时间复杂度为（）。
8、已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最省时间。
9、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中（）。
A、第i行非∞的元素之和
B、第i列非∞的元素之和
C、第i行非∞且非0的元素之和
D、第i列非∞且非0的元素之和
10、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。
二、判断题（认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，
1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可
访问该图的每个顶点。( )
2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅
与表的个数有关，而且与每一块中的元素个数有关。( )
3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。( )
4、图G的最小生成树的代价一定小于其他生成树的代价。( )
5、已知一棵树的先序序列和后序序列，一定能构造出该树。( )
6、对一个堆按层次遍历，不一定能得到一个有序序列。( )
