二分法查找演示课件

mid = (low + high)/2
7
3、查找过程： 将给定值K和mid所指的记录关键字r[mid].key比较
三种可能的结果： （1） K == r[mid].key：
查找成功并结束算法, mid所指的位置就是查到的记录所在的位置。
（2） K < r[mid].key： 修改范围的上界: high = mid -1， 继续对左半部分进行二分查找。
结
1、适用条件：a.有序表
b.顺序存储结构
2、基本思想：逐步缩小查找范围
3、查找过程：定范围，找中间，比较，
循环进行，直到结束
4、算法实现：有效范围：low<=high
若k>r[mid].key low=mid+1
重点难点
若k<r[mid].key high=mid-1
重点
16
/*有效的查找范围*/
{
mid=(low+high)/2;
/*求中点*/
if (k==r[mid].key)
return(mid);
/*找到*/
else
{if (k>r[mid].key) low=mid+1;
/*在右半部分查找/ *
else
high=mid-1;
/*在左半部分查找*/
}
}
return(-1);
（3） K > r[mid].key：
修改范围的下界: low = mid + 1， 继续对右半部分进行二分查找。
重复上述比较过程，区间每次缩小1/2，当区间不断缩小，出现查找区间的 下界大于上界时，宣告查找不成功并结束算法，确定关键字为K的记录不存在。
8
例1：查找k=30的过程：
r表
0 1 2 3 4 5 6 7 8 9 10 11
5
二、基本思想
每次将给定值k与有序表中间位置上 的记录关键字进行比较，确定待查记录 所在的范围，然后逐步缩小查找范围， 直到确定找到或找不到对应记录为止。
6
三、查找过程
1、注意：设有序表记录按关键字升序排列。
2、设置整型变量
low ：指示查找范围的下界 high ：指示查找范围的上界 mid ：指示中间记录所在的位置，
high
（图2：查找k=85的示意图）
失败：下界low> 上界high，说明表中没有关键字值等于85的记录。
10
四、算法实现
1、结点结构类型定义：（假设只有key域）
struct element { int key; };
2、查找表存储结构定义： #define MAXITEM 100 typedef struct element sqlist[MAXITEM];
7.3 二分法查找
节选自《数据结构》 第七章 查找
理工学院： 李 红
1
问题
例：30个学生已按身高从低到高排好了队，新
来的一名学生怎样找到自己的合适位置呢？
顺序查找：特点是算法简单，但查找效率较低。 二分法查找：又称折半查找，是一种查找效率较高的方
法。
问题：1、二分法查找的过程是什么？ 2、二分法查找算法如何实现？
9 13 15 30 37 55 60 75 80 90 92
low
mid
high
（图1：查找k=30的示意图） Nhomakorabea成功：找到了k=30的位序为 4
9
例2：查找k=85的过程：
r表
0 1 2 3 4 5 6 7 8 9 10 11
9 13 15 30 37 55 60 75 80 90 92
low
mid
11
3、二分法查找函数定义
（成功：返回该关键字在表中的位序，否则返回-1）
int bin_search(r, k, n)
sqlist r;
/ *有序表r */
int k;
/ *待查关键字的值 */
int n;
/ *有序表r中记录个数 */
{
int low=1,high=n, mid;
while( low<=high )
/*失败*/
}
12
五. 程序实现
运行程序: 验证二分法查找函数的功能.
13
课后作业
1、编写一程序： 完成班级学生的信息顺序存储，在该信息表上用二分
法查找学号为20和15的学生信息，成功输出该记录的值， 不成功显示“该生不存在”的信息。 2、预习：二叉判定树及二分法查找算法性能分析
14
15
小
2
教学内容
定义及要求 基本思想 查找过程 算法实现
3
重点与难点
重点： 1、查找过程 2、算法实现
难点： 算法实现
4
一、定义及要求
1、二分法查找(Binary Search) 又称折半查找，它是一种查找效率较高
的方法。 2、要求： a、查找表中的记录按关键字有序排列 b、只能在顺序存储结构上实现。