折半查找法PPT课件

二分查找是在我们整个数据结构当中一个比较重要的算法，它的思想在我们的实际开发过程当中应用得非常广泛。

在实际应用中，有些数据序列是已经经过排序的，或者可以将数据进行排序，排序后的数据我们可以通过某种高效的查找方式来进行查找，今天要讲的就是折半查找法(二分查找)，它的时间复杂度为O(logn)，将以下几个方面进行概述了解二分查找的原理与思想分析二分查找的时间复杂度掌握二分查找的实现方法了解二分查找的使用条件和场景1 二分查找的原理与思想在上一个章节当中，我们学习了各种各样的排序的算法，接下来我们就讲解一下针对有序集合的查找的算法—二分查找（Binary Search、折半查找）算法，二分查找呢，是一种非常容易懂的查找算法，它的思想在我们的生活中随处可见，比如说：同学聚会的时候喜欢玩一个游戏——猜数字游戏，比如在1-100以内的数字，让别人来猜从，猜的过程当中会被提示是猜大了还是猜小了，直到猜中为止。

这个过程其实就是二分查找的思想的体现，这是个生活中的例子，在我们现实开发过程当中也有很多应用到二分查找思想的场景。

比如说仙现在有10个订单，它的金额分别是6、12 、15、19、24、26、29、35、46、67 请从中找出订单金额为15的订单，利用二分查找的思想，那我们每一次都会与中间的数据进行比较来缩小我们查找的范围，下面这幅图代表了查找的过程，其中low，high代表了待查找的区间的下标范围，mid表示待查找区间中间元素的下标（如果范围区间是偶数个导致中间的数有两个就选择较小的那个）第一次二分查找第二次二分查找第三次二分查找通过这个查找过程我们可以对二分查找的思想做一个汇总：二分查找针对的是一个有序的数据集合，查找思想有点类似于分治思想。

每次都通过跟区间的中间元素对比，将待查找的区间范围缩小为原来的一半，直到找到要查找的元素，或者区间被缩小为0。

一：查找的数据有序二：每次查找，数据的范围都在缩小，直到找到或找不到为止。

折半查找法的两种实现折半查找法：在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：1）待查找数据值与中间元素值正好相等，则放回中间元素值的索引。

2）待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），知道找到相等的值。

3）待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），知道找到相等的值4）如果最后找不到相等的值，则返回错误提示信息。

按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。

折半查找法的查找次数正好为该值所在的层数。

等概率情况下，约为log2(n+1)-1//Data为要查找的数组，x为待查找数据值，beg为查找范围起始，last 为查找范围终止//非递归法int BiSearch(int data[], const int x, int beg, int last) {int mid;//中间位置if (beg > last){return -1;}while(beg <= last){mid = (beg + last) / 2;if (x == data[mid] ){return mid;}else if (data[mid] < x){beg = mid + 1;}else if (data[mid] > x){last = mid - 1;}}return -1;}//递归法int IterBiSearch(int data[], const int x, int beg, int last){int mid = -1;mid = (beg + last) / 2;if (x == data[mid]){return mid;}else if (x < data[mid]){return IterBiSearch(data, x, beg, mid - 1);}else if (x > data[mid]){return IterBiSearch(data, x, mid + 1, last);}return -1;}//主函数int _tmain(int argc, _TCHAR* argv[]){int data1[60] = {0};int no2search = 45;cout << "The array is : " << endl;int siz = sizeof(data1)/sizeof(int);for (int i = 0; i < siz; i++){data1[i] = i;cout << data1[i] << " ";}cout << endl;int index = -1;//index = BiSearch(data1, no2search, 0, siz);index = IterBiSearch(data1, no2search, 0, siz);cout << "Index of " << no2search << " is " << index << endl;getchar();return 0;}。

#include <stdio.h>#include <stdlib.h>#define LIST_SIZE 20typedef int KeyType;typedef int OtherType;typedef struct{KeyType key;OtherType other_data;}RecordType;typedef struct{RecordType r[LIST_SIZE+1]; /* r[0]为工作单元*/int length;}RecordList;void createlist(RecordList *l,KeyType Key[LIST_SIZE],int KeyNum){int i;l->length =KeyNum;for(i=1; i<=KeyNum; i++){l->r[i].key =Key[i-1];}}int BinSrch(RecordList l, KeyType k)/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/{int low,high,mid;low=1;high=l.length;while(low<=high){mid=(low=high)/2;if(k==l.r[mid].key)return(mid);else{if(k<l.r[mid].key)high=mid-1;elselow=mid=1;}return(0);}}void SortData(RecordList *l){KeyType TempData;for(int i=1; i<l->length; i++)for(int j=i+1; j<=l->length; j++)if(l->r[i].key>l->r[j].key){TempData=l->r[i].key;l->r[i].key=l->r[j].key;l->r[j].key=TempData;TempData=l->r[i].other_data;l->r[i].other_data=l->r[j].other_data;l->r[j].other_data=TempData;}}void Display(RecordList *l){for(int i=1; i<=l->length; i++){printf("%3d ",l->r[i].key);}printf("\n");}void main(){RecordList l;int locate,KeyNum=6;KeyType k,Key[LIST_SIZE]={24,53,90,12,28,45};createlist(&l,Key,KeyNum);printf("排序前输出顺序表:\n");Display(&l);SortData(&l);printf("排序后输出顺序表:\n");Display(&l);printf("请输入要查找的元素:");scanf("%d",&k);locate = BinSrch(l,k);if(locate == 0)printf("未找到!\n");elseprintf("该元素在表中的位置为%d\n",locate); }。

折半查找⼀.题⽬要求·题⽬输⼊n(n<100)个有序正数，请⽤折半查找算法，查找x在其中的位置。

·测试输⼊:5 1,2,3,4,5 2输出:2注：测试集合中，x数⼀定在正数数组中。

即不⽤处理错误逻辑。

⼆.题⽬分析输⼊的第⼀个数是数的个数，第⼆组数是⼀组有序的数，即不需要⾃⼰排序，第三个数则是要查找的数。

折半查找，也称⼆分查找，即利⽤⼆分法进⾏查找。

在某些情况下相⽐于顺序查找，使⽤折半查找算法的效率更⾼。

但是该算法的使⽤的前提是静态查找表中的数据必须是有序的。

三.代码实现#include <stdio.h>int main() {int n, i;int series[100];int t;int right, left, middle;//输⼊scanf_s("%d", &n);for (i = 0; i < n; i++) {scanf_s("%d,", &series[i]);}scanf_s("%d", &t);//初始化left = 0;right = n - 1;middle = (n - 1) / 2;//⼆分法查找while (series[middle] != t) {if (series[middle] < t) right = middle;else left = middle;middle = (left + right) / 2;}printf("%d", middle);return 0;}好吧，上⾯的代码还是运⾏不了（似曾相识）。

调试的时候发现数组元素的输⼊没有成功，但是没有找到错误的原因。

然后我在⽹上找到了⼩刘同学分享的代码。

我这⾥也展⽰⼀下他的源码。

#include <stdio.h>int main(){int num[100];int a,b,flag,i=0;scanf("%d",&a);for(i=0;i<a;i++){scanf("%d,",&num[i]);}scanf("%d",&b);int left=0,right=a-1;while(left<=right){flag = (left+right)/2;if(b==num[flag]){printf("%d",flag+1);break;}if(num[flag] > b)right = flag-1;else if(num[flag] < b)left = flag+1;}}我对⽐了⼀下，除了⼆分查找的实现部分，前⾯的不~TM~是⼀样的吗。