折半查找法

1、首先确定整个查找区间的中间位置 mid=（ left + right） /2 。

2、用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功，若大于，则在后（右）半个区域继续进行折半查找，若小于，则在前（左）半个区域继续进行折半查找。

3、对确定的缩小区域再按折半公式，重复上述步骤。最后得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放。

C++的语言特点：

1、支持数据封装和数据隐藏

在C++中，类是支持数据封装的工具，对象则是数据封装的实现。C++通过建立用户定义类支持数据封装和数据隐藏。

在面向对象的程序设计中，将数据和对该数据进行合法 *** 作的函数封装在一起作为一个类的定义。对象被说明为具有一个给定类的变量。每个给定类的对象包含这个类所规定的若干私有成员、公有成员及保护成员。

完好定义的类一旦建立，就可看成完全封装的实体，可以作为一个整体单元使用。类的实际内部工作隐藏起来，使用完好定义的类的用户不需要知道类是如何工作的，只要知道如何使用它即可。

2、支持继承和重用

在C++现有类的基础上可以声明新类型，这就是继承和重用的思想。通过继承和重用可以更有效地组织程序结构，明确类间关系，并且充分利用已有的类来完成更复杂、深入的开发。新定义的类为子类，成为派生类。它可以从父类那里继承所有非私有的属性和方法，作为自己的成员。

3、支持多态性

采用多态性为每个类指定表现行为。多态性形成由父类和它们的子类组成的一个树型结构。在这个树中的每个子类可以接收一个或多个具有相同名字的消息。当一个消息被这个树中一个类的一个对象接收时，这个对象动态地决定给予子类对象的消息的某种用法。多态性的这一特性允许使用高级抽象。

继承性和多态性的组合，可以轻易地生成一系列虽然类似但独一无二的对象。由于继承性，这些对象共享许多相似的特征。由于多态性，一个对象可有独特的表现方式，而另一个对象有另一种表现方式。

折半查找可以借助于一个二叉树来描述。

为了简化讨论，则把这棵树近似看成满二叉树，设二叉树的高度为h(h>1)

则，根据二叉树的性质，它有最大节点数n=2^h-1，

则h=log2(n+1) (2是底数)。那么二叉树的第j层节点数为：2^(j-1)

假定每个元素的查找概率相等，则，pi=1/n (pi为第i个节点的查找概率)

那么平均查找长度为 1/n*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)）

则经过化简计算，得平均查找长度为：(（n+1）/n ) *log2(n+1)-1 (其中对数中的2为底数：即log以2为底（n+1)的对数）

注 : 当n很大时 ，可近似为 log2(n+1)-1

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找。

而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

扩展资料：

假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。

否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找。

对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。

参考资料来源：百度百科——折半查找法

//参考代码如下：

#include <stdio.h>

int main()

{

int i, j, n, k=0, isFound=0

int num[15] = {88,86,75,74,61,56,52,43,39,34,31,22,18,16,8} //测试数组

printf("请输出一个整数：\n")

scanf("%d", &n)

i = (int)15/2 //对折位移量

j = (int)15/2 //取数“指针”

while(k<2)

{

i = (int)i/2

if(i == 0) k++//i==0 即折半到无可再折时，仍有最后一次比较，故以k做计数

//若未相等，计算下一循环指针的位置

if(n<num[j])

j = j + (i + 1)

else if(n>num[j])

j = j - (i + 1)

else

{

isFound = 1

break //若找到相等数，标记已找到并退出循环

}

}

//输出结果

if(isFound)

printf("该数是数组中第%d个元素的值\n", j)

else

printf("查无此数！\n")

return 0

}

---