查找 顺序查找是一种最基本和最简单的查找方法。它 的思路是,从表中的第一个元素开始,将给定 的值与表中逐个元素的关键字进行比较,直到 两者相符,查到所要找的元素为止。否则就是 表中没有要找的元素,查找不成功。对于表中 记录的关键字是无序的表,只能采用这种方法 描述顺序查找的算法见框图8-1。其中n是表r的 长度,k是要查的元素的关键字,到的元素 的序号
查找 顺序查找是一种最基本和最简单的查找方法。它 的思路是，从表中的第一个元素开始，将给定 的值与表中逐个元素的关键字进行比较，直到 两者相符，查到所要找的元素为止。否则就是 表中没有要找的元素，查找不成功。对于表中 记录的关键字是无序的表，只能采用这种方法。 描述顺序查找的算法见框图8-1。其中n是表r的 长度，k是要查的元素的关键字，i查到的元素 的序号
折半查找又称二分查找,是针对有序表进行查找的简单 有效而又较常用的方法。所谓有序表,即要求表中的 各元素按关键字的值有序(升序或降序)存放。 折半查找不像顺序查找那样,从第一个记录开始逐个顺 序搜索,其基本思想是:首先选取表中间位置的记录, 将其关键字与给定关键字k进行比较,若相等,则查找 成功;否则,若k值比该关键字值大,则要找的元素 定在表的后半部分(或称右子表),则继续对右子表 进行折半查找;若k值比该关键字值小,则要找的元素 定在表的前半部分(左子表),同样应继续对左子 表进行折半查找。每进行一次比较,要么找到要查找 的元素,要么将査找的范围缩小一半。如此递推,直 到査找成功或把要査找的范围缩小为空(查找失败)。 设表的长度为n,表的被查找部分的头为ow,尾为hgh, 初始时,low=1,high=n,k为关键字的值
折半查找又称二分查找，是针对有序表进行查找的简单、 有效而又较常用的方法。所谓有序表，即要求表中的 各元素按关键字的值有序（升序或降序）存放。 折半查找不像顺序查找那样，从第一个记录开始逐个顺 序搜索，其基本思想是：首先选取表中间位置的记录， 将其关键字与给定关键字k进行比较，若相等，则查找 成功；否则，若k值比该关键字值大，则要找的元素一 定在表的后半部分（或称右子表），则继续对右子表 进行折半查找；若k值比该关键字值小，则要找的元素 一定在表的前半部分（左子表），同样应继续对左子 表进行折半查找。每进行一次比较，要么找到要查找 的元素，要么将查找的范围缩小一半。如此递推，直 到查找成功或把要查找的范围缩小为空（查找失败）。 设表的长度为n，表的被查找部分的头为low，尾为high， 初始时，low=1,high=n,k为关键字的值
lowrthieh (1)计算中间记录的序号m2」,取整; (2)若k=rmd]key,成功,否则 若k<rmid]key,则hgh-mid-1,重复(1); 若k>rmid]key,则ow=mid+1,重复(1) 直到成功或不成功(此时 ow>high) 具体算法如下: Void binsrch(struct node rl I, int n, int k) i int mid, low, high, find low=l; high-n, find=0 /置区间初值* while((low<=high) &&(find)) i mid=(low+ high)2 求中点* if(k=rmid].key) find=I 已查到* else if(krImid. key low=mid+1;/在后半区间查找 else highmid-1 在前半区间查找 if(find) return(mid) 查找成功,返回找到元素的位置* Ise return(O); *查找不成功,返回0标记
（2）若k=r[mid].key,成功，否则： 若 k<r[mid].key, 则high=mid―1,重复（1）； 若k>r[mid].key, 则low=mid+1,重复（1）； 直到成功或不成功（此时low>high）。 具体算法如下： Void binsrch(struct node r[ ],int n,int k) { int mid,low,high,find; low=1; high=n;find=0; /*置区间初值*/ while ((low<=high) && (!find)) { mid=(low+high)/2; /*求中点*/ if (k= = r[mid].key) find=1; /*已查到*/ else if(k>r[mid].key ) low=mid+1; /*在后半区间查找*/ else high=mid-1; /*在前半区间查找*/ } if (find) return (mid); /*查找成功，返回找到元素的位置*/ else return (0); /*查找不成功，返回0标记*/ }
采用折半查找,当查找成功时,最少比较次数为 次,如在上例中查找关键字值为18的结点, 只需一次比较。最多经过log2n次比较之后,待 查找子表要么为空,要么只剩下一个结点,所 以要确定查找失败需要log2n次或lg2n+1次比 较。可以证明,折半查找的平均查找长度是: 从折半查找的平均查找长度ASL来看,当表的长 度n很大时,该方法尤其能显示出其时间效率 但由于折半查找的表仍是线性表,若经常要进 行插入、删除操作,则元素排列费时太多,因 此折半查找比较适合于一经建立就很少改动而 又需要经常査找的线性表,较少查找而又经常 需要改动的线性表可以采用链接存储,使用顺 序查找
采用折半查找，当查找成功时，最少比较次数为 一次，如在上例中查找关键字值为18的结点， 只需一次比较。最多经过log2n次比较之后，待 查找子表要么为空，要么只剩下一个结点，所 以要确定查找失败需要log2n次或log2n+1次比 较。可以证明，折半查找的平均查找长度是： 从折半查找的平均查找长度ASL来看，当表的长 度n很大时，该方法尤其能显示出其时间效率。 但由于折半查找的表仍是线性表，若经常要进 行插入、删除操作，则元素排列费时太多，因 此折半查找比较适合于一经建立就很少改动而 又需要经常查找的线性表，较少查找而又经常 需要改动的线性表可以采用链接存储，使用顺 序查找
分块查找 在处理线性表时,如果既希望能够快速查找,又要经常 动态变化,则可以采用分块查找方法。分块查找又称 索引顺序查找,要求将待查的元素均匀的分成块,块 间按大小排序,块内不排序。因此需要建立一个块的 最大(或最小)关键字表,称之为“索引表” 具体而言,假设我们按结点元素关键字升序方式组织表 中各块,则要求第一块中任一结点的关键字值都小于 第二块中所有结点的关键字值;第二块中任一结点的 关键字值都小于第三块中所有结点的关键字值;如此 类推。然后选择每块中的最大(或最小)关键字值组 成索引表。换言之,索引表中的结点个数等于线性表 被分割的块数
分块查找 在处理线性表时，如果既希望能够快速查找，又要经常 动态变化，则可以采用分块查找方法。分块查找又称 索引顺序查找，要求将待查的元素均匀的分成块，块 间按大小排序，块内不排序。因此需要建立一个块的 最大（或最小）关键字表，称之为“索引表” 。 具体而言，假设我们按结点元素关键字升序方式组织表 中各块，则要求第一块中任一结点的关键字值都小于 第二块中所有结点的关键字值；第二块中任一结点的 关键字值都小于第三块中所有结点的关键字值；如此 类推。然后选择每块中的最大（或最小）关键字值组 成索引表。换言之，索引表中的结点个数等于线性表 被分割的块数