从顺序查找过程可以看到（不考虑越界比较i<n）c.取决于所查记录在表中的位置如查找表中第1个记录R[0I时，仅需比较一次；而查找表中最后一个因此，成功时记录R[n-1]时，需比较n次，即c;=i。的顺序查找的平均查找长度为：n(n+1)n+1=pC =-zi=-xASL22sg0n查找成功时的平均比较次数约为表长的一半
11 从顺序查找过程可以看到(不考虑越界比较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 + = + = = = = = 查找成功时的平均比较次数约为表长的一半
9.2.2二分查找二分查找也称为折半查找，要求线性表中的结点必须已按关键字值的递增或递减顺序排列它首先用要查找的关键字与中间位置的结点的关键字相比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成；若不相等，再根据K与该中间结点关键字的比较大小确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的结点或者该线性表中没有这样的结点。服
12 9.2.2 二分查找 二分查找也称为折半查找，要求线性表中的结 点必须已按关键字值的递增或递减顺序排列。 它首先用要查找的关键字k与中间位置的结点 的关键字相比较，这个中间结点把线性表分成了两 个子表，若比较结果相等则查找完成；若不相等， 再根据k与该中间结点关键字的比较大小确定下一 步查找哪个子表，这样递归进行下去，直到找到满 足条件的结点或者该线性表中没有这样的结点
例如，在关键字有序序列(2，4，7，9，1014，18，26，32，40中采用二分查找法查找关键字为7的元素。二分查找过程如下：
13 例如，在关键字有序序列{2，4，7，9，10， 14，18，26，32，40}中采用二分查找法查找关键 字为7的元素。 二分查找过程如下：
开始：0401018263221441low=0high=9mid=(0+9)/2=4第1次比较：21001418263240low=0high=3mid=(0+3)/2=1第2次比较：2101826324014high=3low=2mid=(2+3)/2=2第3次比较：2141826324010R[2].key-7查找成功，返回序号24
14 开始: 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
其算法如下（在有序表R|0.n-1中进行二分查找，成功时返回记录的位置，失败时返回-1）：int BinSearch(SeqList R , int n , KeyType k)intlow=0high=n-1 mid;while (low<-high)mid=(low+high)/2;/*查找成功返回*/if (R[mid].key=-k)return mid;/*继续在R[low..mid-1]中查找*/if (R[mid].key>k)high=mid-1;elselow=mid+1;/*继续在R[mid+1..high]中查找*returnI人15
15 其算法如下(在有序表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; }