发布日期:2015-12-31 11:28 来源: 标签: 编程语言 C教程 C语言查找 C语言二分查找
折半查找又称为二分查找法,这种查找方法有两个条件限制:1:必须采用顺序存储结构,对于链表不适合:2:必须按照关键字大小有序排列;下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
折半查找又称为二分查找法,这种查找方法有两个条件限制:
1:必须采用顺序存储结构,对于链表不适合:
2:必须按照关键字大小有序排列;
具体的算法思想:
对于数组进行比较的时候,比较数组大小的中间值,当发现数据大于该中心数据,就在后面的一个区间进行比较,
如果小于该中心数据,就在前面一个区间进行比较,在新的区间里,再次使用之前的大小中间比较法,比较,直到最后找到该数据为止。
写一个二分法的函数名,包含参数。
int FindBySrch(int * ListData,int ListLength,int KeyData);
写一个循环,在循环中应用折半查找。数组中变换二次区间方法来实现二分查找法:
int FindBySrch(int * ListData,int ListLength,int KeyData)
{
int low = 1;
int hight = ListLength;
while(low <= hight)
{
mid = (low+hight)/2;
if(KeyData > ListData[mid-1])
low = mid;
else if(KeyData < ListData[mid-1])
hight = mid;
else
return mid;
}
return 0;
}

对编好的程序进行测试,得出测试结果:
#include <stdio.h>
int main()
{
int TestData[5] = {34,35,36,89,96};
int retData = FindBySrch(TestData,5,89);
printf("retData:%d\n",retData);
return 0;
}

数据分析:
二分法的优点是比较次数少,查找速度快,平均性能好。缺点是要求查表为顺序表,插入、删除困难,我们这里来算一下,它的平均查找长度是多少:估计长度为n:它的平均查找长度为:log2(n+1)-1 :
注:数组底标和我们开始的底标不一致,我们是从1开始,数组从0开始。

相关评论

专题信息
    C语言是一种计算机程序设计语言。它既有高级语言的特点,又具有汇编语言的特点。它可以作为系统设计语言,编写工作系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的应用程序。C语言对操作系统和系统使用程序以及需要对硬件进行操作的场合,用C语言明显优于其它解释型高级语言,有一些大型应用软件也是用C语言编写的。 C语言具有绘图能力强,可移植性,并具备很强的数据处理能力,因此适于编写系统软件,三维,二维图形和动画。它是数值计算的高级语言。C语言是一种结构化语言。它层次清晰,便于按模块化方式组织程序,易于调试和维护。