折半查找算法

p62273470

以下讨论的有序数列均是从小到大排列的！
什么是折半查找？
答：折半查找是一种效率较高的查找算法。折半查找的先决条件是查找表中的数据元素排列必须是有序的。折半查找先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，可以将查找区间缩小一半，它可以明显减少比较次数，提高查找效率。


方法分析：
折半查找先以有序数列的中点位置为比较对象，比较会产生3种情况，一种是待查找值大于中点位置的数，此时我们要把比较区间缩小为有序数列的后半部分；一种是待查找值小于中点位置的数，此时我们要把比较区间缩小为有序数列的前半部分；一种是待查找值等于中点位置的数，此时查找成功。这样不断比较，直到查找成功或者区间小于0，就停止查找！

数据结构设计：
有序数列：用一个数组data[size]来存放。
区间：区间用数组的两个下标表示。用整型low，high下标来表示区间的前端点，后端点。mid表示数组的中间位置下标。如：

   7   14   18   21   23   29   31   35   38    52
   ↑ low                    ↑ mid                            ↑ high
                             (mid=(low+high)/2)


代码如下：

1. //折半查找
   
2. 
   
3. #include<iostream.h>
   
4. 
   
5. int Binary_Search(int *da,int s)
   
6. /*da为有序数列的头指针，s是要查找的数值*/
   
7. {
   
8. int low,high,mid;
   
9. int count; //保存查找次数
   
10. int flag; //flag用来保存在数组中第几个位置查找到待查找值
    
11. low=0;
    
12. count=1;
    
13. high=10;
    
14. flag=0;
    
15. while(low<=high)
    
16. {
    
17. mid=(low+high)/2;
    
18. 
    
19. if(s<da[mid]) //待查找值s小于中值
    
20. high=mid-1;
    
21. 
    
22. else if(s>da[mid]) //待查找值s大于中值
    
23. low=mid+1;
    
24. 
    
25. else{ //待查找值s等于中值
    
26. flag=mid;
    
27. break;
    
28. }
    
29. count++;
    
30. }
    
31. cout<<"查找的次数是："<<count<<endl;
    
32. return flag+1;
    
33. }
    
34. 
    
35. void main(){
    
36. int i;
    
37. int s;
    
38. int data[10] = {7,14,18,21,23,29,31,35,38,52};
    
39. cout<<"请输入要查找的的元素："<<endl;
    
40. cin>>s;
    
41. i=Binary_Search(data,s);
    
42. if(i==0)
    
43. cout<<"你妹，找不到所要查找的元素！"<<endl;
    
44. else
    
45. cout<<"所要查找的数据元素"<<s<<"的位置是"<<i<<endl;
    
46. }
    
47. 
    

复制代码

嗜血灵异狂

算法真是中级编程知识  语言都还没入门呢  不敢看了

驻留的习惯

先藏着！！！！！！！！！！！

shenyaowen

厉害哦 加油:shy::shy::shy::shy::shy:

じO-联合

归并排序吗？？？？

qaed

居然不设隐藏{:1_1:}{:1_1:}{:1_1:}{:1_1:}

Fly_Sheep

其实算法才是程序的灵魂

rockerz

如果只是简单的查找，可以用 #include <alogrithm> 中的 binary_search(),upper_bound和lower_bound(). 具体可以自己去查查。

cable5881

谢谢楼主分享！！！！！！！！

vanentu

ThanksFORshare

EntU

其实算法才是程序的灵魂

vank

到这，我好兴奋

zndownload

比较基本的算法！