(4)若事先知道表中各结点的查找概率不相 等和它们的分布情况,则应将表中结点按查找 概率由小到大地存放,以便提高顺序查找的效 率。为了提高查找效率,对算法 Seqsearch做如 下修改:每当查找成功,就将找到的结点和其 后继(若存在结点交换。这样,使得查找概率 大的结点在查找过程中不断往后移,便于在以 后的查找中减少比较次数。 <心 武汉理工大学华派出
武汉理工大学华夏学院-信息工程 系 （4) 若事先知道表中各结点的查找概率不相 等和它们的分布情况，则应将表中结点按查找 概率由小到大地存放，以便提高顺序查找的效 率。为了提高查找效率，对算法SeqSearch做如 下修改：每当查找成功，就将找到的结点和其 后继(若存在)结点交换。这样， 使得查找概率 大的结点在查找过程中不断往后移，便于在以 后的查找中减少比较次数
④顺序查找的优点 算法简单,且对表的结构无任何要求,无论是 用向量还是用链表来存放结点,也无论结点之 间是否按关键字有序,它都同样适用。 ⑤顺序查找的缺点 查找效率低因此当n较大时不宜采用顺序查找。 武汉理I气光先能信息工程
武汉理工大学华夏学院-信息工程 系 ④顺序查找的优点 ⑤顺序查找的缺点 查找效率低,因此,当n较大时不宜采用顺序查找。 算法简单，且对表的结构无任何要求，无论是 用向量还是用链表来存放结点，也无论结点之 间是否按关键字有序，它都同样适用
(二)折半(二分)查找 1、二分查找 Binary Search) 二分查找又称折半查找,它是一种效率较高 的查找方法 分查找要求:线性表是有序的,即表中结 点按关键字从小到大(或从大到小),并且要用 向量作为表的存储结构(即用顺序存储方法进行 存储)。不妨设有序表是递增有序的 2、二分查找的基本思想 二分查找的基本思想是:(设R[ oWhigh]是 当前的查找区间) 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （二） 折半（二分）查找 1、二分查找(Binary Search) 二分查找又称折半查找，它是一种效率较高 的查找方法。 二分查找要求：线性表是有序的，即表中结 点按关键字从小到大（或从大到小），并且要用 向量作为表的存储结构（即用顺序存储方法进行 存储）。不妨设有序表是递增有序的。 2、二分查找的基本思想 二分查找的基本思想是:（设R[low..high]是 当前的查找区间）
(1)首先确定该区间的中点位置: mid=( low+ high )/2 其中 low为左界结点下标,high为右界结点下标。 (2)然后将待查的K值与R[mid]key比较: 若相等则查找成功并返回此位置,否则须确定 新的查找区间继续二分查找具体方法如下: ①若Rmid]key>K,则由表的有序性可知 R[mid.n].keys均大于K,因此若表中存在关 键字等于K的结点,则该结点必定是在位置 mid左边的子表 R[loW. mid-1]中,故新的查 找区间是左子表R[ oW. mid-1]。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 (1)首先确定该区间的中点位置： mid＝（low＋high）/2 其中： low为左界结点下标，high为右 界结点下标。 (2)然后将待查的K值与R[mid].key比较： 若相等,则查找成功并返回此位置,否则须确定 新的查找区间,继续二分查找,具体方法如下： ①若R[mid].key>K，则由表的有序性可知 R[mid..n].keys均大于K，因此若表中存在关 键字等于K的结点，则该结点必定是在位置 mid左边的子表R[low..mid-1]中，故新的查 找区间是左子表R[low..mid-1]
②类似地,若R[rmid]key<K,则要查找的K必 在mid的右子表R[md+1high中即新的查找 区间是右子表R[mid+1 high].下一次查找是针 对新的查找区间进行的。 因此,从初始的查找区间R[1…m开始此时 low=1high=n。每经过一次与当前查找区间 的中点位置上的结点关键字的比较,就可确定查 找是否成功不成功则当前的查找区间就缩小 半这一过程重复直至找到关键字为K的结点或 者直至当前的查找区间为空即查找失败)时为止。 <心 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 ②类似地，若R[mid].key <K，则要查找的K必 在mid的右子表R[mid+1..high]中,即新的查找 区间是右子表R[mid+1..high]. 下一次查找是针 对新的查找区间进行的。 因此，从初始的查找区间R[1..n]开始,,此时 low＝1,high＝n。每经过一次与当前查找区间 的中点位置上的结点关键字的比较, 就可确定查 找是否成功, 不成功则当前的查找区间就缩小一 半.这一过程重复直至找到关键字为K的结点, 或 者直至当前的查找区间为空(即查找失败)时为止