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