C语言：数据结构-线性表的查找-折半查找

折半查找

（1）折半查找的存储结构文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

查找表（顺序表）中记录所相应的关键字必需有序。文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

（2）折半查找的基本思想文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

从有序表的中间位置元素开始查找，若没有查到，可以排除了掉大约一半的元素，缩小查找规模，反复上述进程。文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

结构数组a中寄存查找表的元素，查找规模[0、n-1]，Low下界，high上界，mid中间位置，查找值 k。文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

1.low= 0，high =n-1文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

2.mid=（Low+high）/2文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

3.若 k==a [mid].key，返回mid文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

k< a [mid].key，high = mid-1 （取前半区间）文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

k> a [mid].key，low = mid+1 （取后半区间）文章源自微观生活（93wg.com）微观生活-https://93wg.com/20081.html

重复①～③，直到Low>high，说明整个表已查找终了，此时若表中仍查不到关键字为K的记录，则查找失败。

例8-1：设顺序表中有8个记录，它们的关键字顺次为{8，11，18，28，45，55，63，80}，用折半查找的办法在该顺序表中查找关键字为55以及20的记录。查找关键字为55的记录的进程见图8-1：

初始状况时low=0，high=7，mid=⌊（0+7）/2⌋=3，low指向a[0].key=8，mid指向a[3].key=28，high指向a[7].key=80，见图8-1（a）。k=55，将k与a[mid].key相比较，k>a[mid].key，表明若待查记录存在，则必然在区间[mid+1，high]中，所以，此时令low=mid+1，有low=4，high=7，从而求得新的mid=⌊（4+7）/2⌋=5，见图8-1（b）。k继续与a[mid].key进行比较，因为k= =a[mid].key，查找胜利，返回记录的下标为5。

折半查找进程示用意

若查找关键字为20的记录，则其查找进程见图8-2。初始状况时low=0，high=7，mid=⌊（0+7）/2⌋=3，low指向a[0].key=8，mid指向a[3].key=28，high指向a[7].key=80，见图8-2 （a）。由于k<a[mid].key，所以令high=mid-1，mid=⌊（0+2）/2⌋=1，见图8-2（b），继续比较，又由于k>a[mid].key，所以令low=mid+1，mid=⌊（2+2）/2⌋=2，见图8-2（c）。

折半查找进程示例

k>a[mid].key，所以令low=mid+1，low=3，low>high，说明整个表已经查询终了，没有找到关键字等于k的记录，查找失败。

折半查找算法int Binary_Search(NODE a[],int n, int k)/* 在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找胜利返回该记录的下标，失败时返回-1 */{int low,mid,high;low=0;high=n-1;while(low<=high){mid=(low+high)/2;if(a[mid].key==k)return mid; /*查找胜利，返回查找到的记录的下标*/else if(a[mid].key<k)low=mid+1; /*取后半查找区间*/else high=mid-1; /*取前半查找区间*/}return -1; /*查找失败*/}

（4）折半查找对应的断定树

折半查找的进程可以用一棵二叉树来描写，树中的每一个结点相应于查找表中的一个记录，结点的值为相应记录在查找表中的位置值。根结点的值是查找表的中间元素的下标，左子树的结点是关键字小于中间元素的左子表，左子树的根结点是左子表的中间元素的下标；右子树的结点是关键字大于中间元素的右子表，右子树的根结点是右子表的中间元素的下标，顺次类推得到相应的断定树。

设查找表为（6，14，20，21，38，56，68，78，85，85，100），元素的下标位置顺次为0，1，2，…，10，相应的断定树如图8-3所示，从表中看出查找21要经由3次比较，查找100要经由4次比较。在等几率前提下，可求得胜利查找的平均查找长度为：

ASL=(1+2*2+3*4+4*4)/11=3

折半查找对应的断定树

当查找胜利时，最佳情况下的比较次数为1次。而查到每一个记录的比较次数等于该结点在断定树中的深度。折半查找算法的时间繁杂度为O（log2n）。很显然，折半查找的效力要比顺序查找高的多。然而，该办法只合用于顺序存储结构的有序表，没有顺序查找使用的规模广。

折半查找算法不合适链表结构的序列。尽管有序的单链表的结点是按从小到大（或从大到小）顺序排列的，但因其存储结构为单链表，查找结点时只能从头指针开始顺序查找，不能进行随机查找，所以不合适采取折半查找。

以上就是微观生活（93wg.com）关于“C语言：数据结构-线性表的查找-折半查找”的详细内容，希望对大家有所帮助！