折半查找算法
本帖最后由 p62273470 于 2011-12-5 17:51 编辑以下讨论的有序数列均是从小到大排列的！
什么是折半查找？
答：折半查找是一种效率较高的查找算法。折半查找的先决条件是查找表中的数据元素排列必须是有序的。折半查找先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，可以将查找区间缩小一半，它可以明显减少比较次数，提高查找效率。
方法分析：
折半查找先以有序数列的中点位置为比较对象，比较会产生3种情况，一种是待查找值大于中点位置的数，此时我们要把比较区间缩小为有序数列的后半部分；一种是待查找值小于中点位置的数，此时我们要把比较区间缩小为有序数列的前半部分；一种是待查找值等于中点位置的数，此时查找成功。这样不断比较，直到查找成功或者区间小于0，就停止查找！
数据结构设计：
有序数列：用一个数组data来存放。
区间：区间用数组的两个下标表示。用整型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) //待查找值s小于中值
high=mid-1;
else if(s>da) //待查找值s大于中值
low=mid+1;
else{ //待查找值s等于中值
flag=mid;
break;
}
count++;
}
cout<<"查找的次数是："<<count<<endl;
return flag+1;
}
void main(){
int i;
int s;
int data = {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;
}
算法真是中级编程知识语言都还没入门呢不敢看了 先藏着！！！！！！！！！！！ 厉害哦 加油:shy::shy::shy::shy::shy: 归并排序吗？？？？ 居然不设隐藏{:1_1:}{:1_1:}{:1_1:}{:1_1:} 其实算法才是程序的灵魂 如果只是简单的查找，可以用 #include <alogrithm> 中的 binary_search(),upper_bound和lower_bound(). 具体可以自己去查查。 谢谢楼主分享！！！！！！！！ ThanksFORshare 其实算法才是程序的灵魂 到这，我好兴奋 比较基本的算法！
页:
[1]