从顺序查找过程可以看到(不考虑越界比较<n),c取决于 所查记录在表中的位置。如查找表中第1个记录R0时仅需 比较一次;而查找表中最后一个记录Rm-1时需比较m次,即 c=i。因此成功时的顺序查找的平均查找长度为: 1n(n+1)n+1 ASL=∑ ∑i=- sq n i=1 n 2 2 查找成功时的平均比较次数约为表长的一半
从顺序查找过程可以看到(不考虑越界比较i<n),ci取决于 所查记录在表中的位置。如查找表中第1个记录R[0]时,仅需 比较一次；而查找表中最后一个记录R[n-1]时,需比较n次,即 ci=i。因此,成功时的顺序查找的平均查找长度为： 2 n 1 2 n(n 1) n 1 i n 1 i c i p s q ASL n i 1 n i 1 + = + = = = = = 查找成功时的平均比较次数约为表长的一半
10.2.2二分查找 二分查找也称为折半查找要求线性表中的结点必须己按关键 字值的递增或递减顺序排列。它首先用要查找的关键字k与中 间位置的结点的关键字相比较这个中间结点把线性表分成了两 个子表若比较结果相等则查找完成;若不相等再根据k与该中 间结点关键字的比较大小确定下一步查找哪个子表这样递归进 行下去直到找到满足条件的结点或者该线性表中没有这样的结 点
10.2.2 二分查找 二分查找也称为折半查找要求线性表中的结点必须己按关键 字值的递增或递减顺序排列。它首先用要查找的关键字k与中 间位置的结点的关键字相比较,这个中间结点把线性表分成了两 个子表,若比较结果相等则查找完成;若不相等,再根据k与该中 间结点关键字的比较大小确定下一步查找哪个子表,这样递归进 行下去,直到找到满足条件的结点或者该线性表中没有这样的结 点
例如,在关键字有序序列{2,4,7,9,10,14,18,26,32,40}中采用二 分查找法查找关键字为7的元素。 二分查找过程如下:
例如,在关键字有序序列{2,4,7,9,10,14,18,26,32,40}中采用二 分查找法查找关键字为7的元素。 二分查找过程如下：
开始:2479101418263240 lOw=0 mid=(0+9)2=4 第1次比较:2479101418263240 low=0 high=3 mid=(0+3)2=1 第2次比较:2479101418263240 low=2 high=3 mid=(2+3)/2=2 第3次比较:2479101418263240 R2.key=7 查找成功返回序号2
开始: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=(0+9)/2=4 第1次比较: 2 4 7 9 10 14 18 26 32 40 low=0 high=3 mid=(0+3)/2=1 第2次比较: 2 4 7 9 10 14 18 26 32 40 low=2 high=3 mid=(2+3)/2=2 第3次比较: 2 4 7 9 10 14 18 26 32 40 R[2].key=7 查找成功,返回序号2
其算法如下(在有序表R0.n-1中进行二分查找成功时返回记 录的位置失败时返回-1): int BinSearch(seq list R, int n, KeyType k) int low=0, high=n-l, mid; while (low<=high) mid=(lowthigh)/2 if(R| mid]. key=k)/查找成功返回 return mid if(R| mid]. key>k)/继续在Row.mid-1中查找* high=mid-1; ese low=mid+1;/继续在 TImid+1.high中查找* return -1
其算法如下(在有序表R[0..n-1]中进行二分查找,成功时返回记 录的位置,失败时返回-1)： int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid; while (low<=high) { mid=(low+high)/2; if (R[mid].key==k) /*查找成功返回*/ return mid; if (R[mid].key>k) /*继续在R[low..mid-1]中查找*/ high=mid-1; else low=mid+1; /*继续在R[mid+1..high]中查找*/ } return -1; }