折半查找（二分查找）折半查找（二分查找）折半查找（二分查找）
需积分: 47 110 浏览量
2009-12-30
22:11:02
上传
评论
收藏 35KB DOCX 举报
有序表的查找
对于以数组方式存贮的记录，如果数组中各个记录的次序是按其关键字值的大小顺序排列
的，则称为有序数组或有序表。
折半查找
对顺序分配的有序表可以采用折半查找 (Binary Search) ，又称二分查找。
1.基本思想
从第 1 个记录开始逐个顺序搜索，而是每次把要找的给定值 K ，与在中间位置的记录的关
键字值进行比较。设有序记录数组 r 中每个记录的关键字值按升序排列为：
r
0
. key ， r
1
.key ， r
2
.key ，…， r
m
.key ，…,r
n-1
.key
其中， n 为记录个数。当 i ＜ j 时，有 r
i
.key ≤ r
j
.key 。开始时，中间位置记录的序号为 m
＝ [(n ＋ 1)/2] ，相应的关键字值为 r
m
.key 。将给定值 K 与 r
m
.key 比较，有三种可能的结果：
(1) K ＝ r
m
.key
查找成功，结束查找。
(2) K ＜ r
m
.key
由于各记录的关键字值是由小到大排列的，因此，如果要查找的记录存在，必定在有序表
的左半部分。于是，对左半部分继续使用折半查找进行搜索，但搜索区间缩小了一半。
(3) K ＞ r
m
.key。
如果要查找的记录存在，则必定在有序表的右半部分于是，对右半部分继续使用折半查找
进行搜索，但搜索区间缩小了一半。
这样在查找过程中，搜索区间不断对分并成指数地缩小，因而查找速度明显地快于顺序查
找。当最后只剩下一个记录，而且此记录不是要找的记录，则宣告查找失败。
2.折半查找的算法
void binary_search(KeyType K,datalist r[],int n,)
{ int m,low ,high,*nd;
low=0;high=n-1;*nd=0;
do{ m=(low+high)/2;
if(K==r[m].key)
{ cout<<"查找成功，该记录对应的下标为："<<m<<endl;
*nd=1;
}
else if(K<r[m].key)high=m-1;
else low=m+1;
}while((*nd==0)&&(low<=high));
if(*nd==0)cout<<"查找失败！";
}
3.折半查找性能分析
算法中每次将给定值 K 与中间位置记录的关键字值进行比较，最理想的情况是一次比较成
功，那么，在最坏的情况下，要做多少次比较呢？不妨看看具体统计：
资源评论
