x'3.二分查找的性能分析 为了分析二分査找的性能,可以用二叉树来描述二分查找 过程。把当前查找区间的中点作为根结点,左子区间和右 子区间分别作为根的左子树和右子树,左子区间和右子区 间再按类似的方法,由此得到的二叉树称为二分查找的判 定树。例如,图8-1给定的关键字序列 8,17,25,44,68,77,98,100,115,125,的判定树见图8-3 图8-3具有10个关键字序列的二分查找判定树
3.二分查找的性能分析 为了分析二分查找的性能，可以用二叉树来描述二分查找 过程。把当前查找区间的中点作为根结点，左子区间和右 子区间分别作为根的左子树和右子树，左子区间和右子区 间再按类似的方法，由此得到的二叉树称为二分查找的判 定 树 。 例 如 ， 图 8-1 给定的关键字序列 8,17,25,44,68,77,98,100,115,125，的判定树见图8-3。 44 8 25 17 98 77 68 100 115 125 图 8-3 具有 10 个关键字序列的二分查找判定树
x从图8-3可知,查找根结点68,需一次查找,查找17和 100,各需二次查找,查找8、25、77、115各需三次查 氵找,查找44、98、125各需四次查找。于是,可以得到 结论:二叉树第K层结点的查找次数各为k次(根结点为 第1层),而第k层结点数最多为2k1个。假设该二叉树的 深度为h,则二分查找的成功的平均查找长度为(假设 每个结点的查找概率相等): ASI=∑PC=1/nSc≤1/n(1+2×2+3×22+.+h×2h) 因此,在最坏情形下,上面的不等号将会成立,并根据 二叉树的性质,最大的结点数n=2h-1,h-log(n+1),于是 可以得到平均查找长度ASL=(n+1)nlog(n+1)-1。该公式 可以按如下方法推出:
从图8-3 可知，查找根结点68，需一次查找，查找17和 100，各需二次查找，查找8、25、77、115各需三次查 找，查找44、98、125各需四次查找。于是，可以得到 结论：二叉树第K层结点的查找次数各为k次(根结点为 第1层)，而第k层结点数最多为2 k-1个。假设该二叉树的 深度为h， 则二分查找的成功的平均查找长度为（假设 每个结点的查找概率相等）： = n i i i p c 1 = n i i c 1 ASL= =1/n ≤1/n（1+22+32 2+…+h2 h-1）， 因此，在最坏情形下，上面的不等号将会成立 ，并根据 二叉树的性质，最大的结点数n=2 h -1，h=log2 (n+1) ，于是 可以得到平均查找长度ASL=(n+1)/n log2 (n+1)-1。该公式 可以按如下方法推出：
c?设sk2=20+2+32++(h-1)2+h21 则2s2+2.22+.+(h-2),2h2+h1).2h1+h2h 22S-s h.2(20+2+22+..+2h2+2 h2h-(2h-1) =log2(n+1)(n+1)-n 所以,ASL=sn(n+1nlog2(n+1)1 当n很大时,ASL≈log2m+1)-1可以作为二分查找成功 时的平均查找长度,它的时间复杂度为O(og2n
= − h k k k 1 1 设 2 s= =2 0+2.2 1+3.2 2+…+(h-1).2 h-2+h.2 h-1 则2s=2 1+2.2 2+…+(h-2).2 h-2+h-1).2 h-1+h.2 h s=2s-s =h .2 h -(2 0+2 1+2 2+…+2 h-2+2 h-1 ) =h .2 h -(2 h -1) = log2 (n+1).(n+1)-n 所以，ASL=s/n=(n+1)/n log2 (n+1)-1。 当n很大时，ASL log2 (n+1)-1 可以作为二分查找成功 时的平均查找长度，它的时间复杂度为O(log2 n)
823索引查找 1索引查找的思想 索引査找,又称分级査找,它既是一种査找方法,又是 种存贮方法,称为索引存贮。它在我们的日常生活中 有着广泛的应用。例如,在汉语字典中查找某个汉字时, 若知道某个汉字读者,则可以先在音节表中查找到对应 正文中的页码,然后再在正文中所对应的页中查出待查 的汉字;若知道该汉字的字形,但不知道读者,则可以 先在部首表中根据字的部首查找到对应检字表中的页码, 再在检字表中根据字的笔画找到该汉字所在的页码。在 这里,整个字典就是索引查找的对象,字典的正文是字 典的主要部分,被称之为主表,而检字表,部首表和音 节表都有是为了方便查找主表而建立的索引,所以被称 之为索引表
8.2.3 索引查找 1.索引查找的思想 索引查找，又称分级查找，它既是一种查找方法，又是 一种存贮方法，称为索引存贮。它在我们的日常生活中 有着广泛的应用。例如，在汉语字典中查找某个汉字时， 若知道某个汉字读者，则可以先在音节表中查找到对应 正文中的页码，然后再在正文中所对应的页中查出待查 的汉字；若知道该汉字的字形，但不知道读者，则可以 先在部首表中根据字的部首查找到对应检字表中的页码， 再在检字表中根据字的笔画找到该汉字所在的页码。在 这里，整个字典就是索引查找的对象，字典的正文是字 典的主要部分，被称之为主表，而检字表，部首表和音 节表都有是为了方便查找主表而建立的索引，所以被称 之为索引表
飞它在索引查找中,主表只有一个,其中包含的是待查找的 内容,而索引表可以有多个,包含一级索引,二级索 引….…,所需的级数可根据具体问题而定。如刚才的利 用读音查找汉字为一级索引,而利用字形查找汉字为 级索引(部首表→检字表→汉字)。在此,我们仅讨论 级索引。 索引查找是在线性表(主表)的索引存贮结构上进行的, 而索引存贮的基本思想是:首先将一个线性表(主表)按 入照一定的规则分成若干个逻辑上的子表,并为每个子表分 别建立一个索引项,由所有这些索引项得到主表的一个索 引表,然后,可采用顺序或链接的方法来存储索引表和各 个子表。索引表中的每个索引项通常包含三个域:一是索 引值域,用来存储标识对应子表的索引值,它相当于记录 的关键字,在索引表中由此索引值来唯一标识一个索引项 (子表);二是子表的开始位置,用来存储对应子表的第 个元素的存储位置;三是子表的长度,用来存储对应子 表的元素个数
在索引查找中，主表只有一个，其中包含的是待查找的 内容，而索引表可以有多个，包含一级索引，二级索 引……，所需的级数可根据具体问题而定。如刚才的利 用读音查找汉字为一级索引，而 利用字形查找汉字为二 级索引（部首表→检字表→汉字）。在此，我们仅讨论 一级索引。 索引查找是在线性表（主表）的索引存贮结构上进行的， 而索引存贮的基本思想是：首先将一个线性表（主表）按 照一定的规则分成若干个逻辑上的子表，并为每个子表分 别建立一个索引项，由所有这些索引项得到主表的一个索 引表，然后，可采用顺序或链接的方法来存储索引表和各 个子表。索引表中的每个索引项通常包含三个域：一是索 引值域，用来存储标识对应子表的索引值，它相当于记录 的关键字，在索引表中由此索引值来唯一标识一个索引项 （子表）；二是子表的开始位置，用来存储对应子表的第 一个元素的存储位置；三是子表的长度，用来存储对应子 表的元素个数