马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 p62273470 于 2011-12-5 17:51 编辑
以下讨论的有序数列均是从小到大排列的！
什么是折半查找？
答：折半查找是一种效率较高的查找算法。折半查找的先决条件是查找表中的数据元素排列必须是有序的。折半查找先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，可以将查找区间缩小一半，它可以明显减少比较次数，提高查找效率。
方法分析：
折半查找先以有序数列的中点位置为比较对象，比较会产生3种情况，一种是待查找值大于中点位置的数，此时我们要把比较区间缩小为有序数列的后半部分；一种是待查找值小于中点位置的数，此时我们要把比较区间缩小为有序数列的前半部分；一种是待查找值等于中点位置的数，此时查找成功。这样不断比较，直到查找成功或者区间小于0，就停止查找！
数据结构设计：
有序数列：用一个数组data[size]来存放。
区间：区间用数组的两个下标表示。用整型low，high下标来表示区间的前端点，后端点。mid表示数组的中间位置下标。如：
7 14 18 21 23 29 31 35 38 52
↑ low ↑ mid ↑ high
(mid=(low+high)/2)
代码如下：
//折半查找
#include<iostream.h>
int Binary_Search(int *da,int s)
/*da为有序数列的头指针，s是要查找的数值*/
{
int low,high,mid;
int count; //保存查找次数
int flag; //flag用来保存在数组中第几个位置查找到待查找值
low=0;
count=1;
high=10;
flag=0;
while(low<=high)
{
mid=(low+high)/2;
if(s<da[mid]) //待查找值s小于中值
high=mid-1;
else if(s>da[mid]) //待查找值s大于中值
low=mid+1;
else{ //待查找值s等于中值
flag=mid;
break;
}
count++;
}
cout<<"查找的次数是："<<count<<endl;
return flag+1;
}
void main(){
int i;
int s;
int data[10] = {7,14,18,21,23,29,31,35,38,52};
cout<<"请输入要查找的的元素："<<endl;
cin>>s;
i=Binary_Search(data,s);
if(i==0)
cout<<"你妹，找不到所要查找的元素！"<<endl;
else
cout<<"所要查找的数据元素"<<s<<"的位置是"<<i<<endl;
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2011-12-5 17:51:46
置顶卡
千斤顶
显身卡
发表于 2014-3-15 20:55:32