📄 ds9.2.2.htm
字号:
<p align="left"><font size="5" color="#FFFFFF"><b>关键字21的查找过程为：</b></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p align="center"><img border="0" src="对分4.gif" width="588" height="105"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>56>21,故high=mid-1;</b></font></p>
<p align="center"><img border="0" src="对分5.gif" width="561" height="105"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>19<21,故low=mid+1;</b></font></p>
<p align="center"><img border="0" src="对分6.gif" width="541" height="126"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>21=21,查找成功，返回mid值;</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体">
<p align="left"><font size="5" color="#FFFFFF"><b>关键字85的查找过程为：</b></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p align="center"><img border="0" src="对分4.gif" width="588" height="105"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>56<85,故low=mid+1;</b></font></p>
<p align="center"><img border="0" src="对分7.gif" width="568" height="105"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>80<85,故low=mid+1;</b></font></p>
<p align="center"><img border="0" src="对分8.gif" width="568" height="126"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>88>85,故high=mid-1;</b></font></p>
<p align="center"><img border="0" src="对分9.gif" width="541" height="126"></p>
<p align="center"><font size="5" color="#FFFFFF"><b>此时，low>high，查找不成功，返回0</b></font></p>
<p align="left"><b><font size="5" color="#FFFFFF">算法可描述为：</font></b></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">int search_Bin(SSTable
ST,KeyType key)</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">{
low=1;high=ST.length;</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
while(low<=high)</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
{ mid=(low+high)/2;</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
if(ST.elem[mid].key==key) return mid;</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5"><font color="#FFFFFF">
</font><font color="#FFFFFF">else
if(ST.elem[mid].key>key) high=mid-1;</font></font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
else
low=mid+1;</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
}</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
return 0;</font></b>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">} </font></b>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><b><font size="5" color="#FFFFFF">【性能分析】</font></b></span></p>
<font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US"> </span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。</span></b></font>
<p> <font size="5" color="#FFFFFF"><b> 由上例中查找过程可知，找第6个数据元素只须比较1次，找第3、9个数据元素须比较2次，找第1、4、7和10个数据元素须比较3次，找第5、2、8和11个数据元素须比较4次；表示为对分查找的判定树如下：</b></font></p>
<p align="center"><img border="0" src="对分1.gif" width="449" height="245"></p>
<p align="left"><font size="5" color="#FFFFFF">
判定树叶子结点所在的层次最多相差一层，且它接近于一棵满二叉树，由于满二叉树结点数n与深度h之间满足n=2<sup>h</sup>-1,因此取h=log<sub>2</sub>(n+1),第k层上结点个数为2<sup>k-1</sup>,此时可以求得对分查找在等概率情况下的平均查找彻底为：</font></p>
<p align="left"><font size="5" color="#FFFFFF"> ASL=<b><img border="0" src="查找1.gif" align="middle" width="56" height="125">P<sub>i</sub>C<sub>i</sub>=<img border="0" src="线性2.gif" align="middle" width="40" height="73"><img border="0" src="查找1.gif" align="middle" width="56" height="125">C<sub>i</sub>=<img border="0" src="对分2.gif" align="middle" width="56" height="73">log<sub>2</sub>(n+1)-1</b></font></p>
<p align="left"><font size="5" color="#FFFFFF"> 当n>50时可以近似为:</font></p>
<p align="left"><font size="5" color="#FFFFFF">
ASL=log<sub>2</sub>(n+1)-1</font></p>
<p align="left"><font size="5" color="#FFFFFF"> 可知，对分查找的ASL小于顺序查找的ASL，但它要求须按关键字进行排序，且当n较小时（n<30）ASL也不是较理想。</font></p>
<p align="left"> </p>
<p align="center"><b><font size="5"><a href="ds9.2.HTM"><font color="#FFFF00">返回</font></a></font></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -