page337.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 69 行
HTML
69 行
<HTML><HEAD><TITLE>Binary Search</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5076" HREF="page338.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5074" HREF="page335.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5070" HREF="page336.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5078" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010622000000000000000">Binary Search</A></H3><P>We can improve the performance of the <I>M</I>-way search treesearch algorithm by recognizing thatsince the keys are kept in a sorted array,we can do a binary search rather than a linear search.Program <A HREF="page337.html#progmWayTreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an alternate implementationfor the <tt>find</tt> method of the <tt>MWayTree</tt> class.This method makes use of the <tt>findIndex</tt> methodwhich does the actual binary search.<P><P><A NAME="21038"> </A><A NAME="progmWayTreed"> </A> <IMG WIDTH=575 HEIGHT=485 ALIGN=BOTTOM ALT="program20917" SRC="img1315.gif" ><BR><STRONG>Program:</STRONG> <tt>MWayTree</tt> class <tt>findIndex</tt> and <tt>find</tt> methods (binary search).<BR><P><P>The <tt>findIndex</tt> method as its argument an object, say <I>x</I>,and returns an <tt>int</tt> in the range between 0 and <I>n</I>-1,where <I>n</I> is the number of subtrees of the given node.The result is the largest integer <I>i</I>, if it exists,such that <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64859" SRC="img1316.gif" > where <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" > is the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > key.Otherwise, it returns the value 0.<P><tt>findIndex</tt> determines its result by doing a binary search.In the worst case, <IMG WIDTH=124 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64867" SRC="img1317.gif" >iterations of the main loop (lines 8-13)are required to determine the correct index.One object comparison is done before the loop (line 4)and one comparison is done in each loop iteration (line 10).Therefore, the running time of the <tt>findIndex</tt> method is<P> <IMG WIDTH=387 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64843" SRC="img1318.gif" ><P>If <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64143" SRC="img1239.gif" >, this simplifies to <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64871" SRC="img1319.gif" >.<P>The <tt>find</tt> method of the <tt>MWayTree</tt> classdoes the actual search.It calls <tt>findIndex</tt> to determine largest integer <I>i</I>, if it exists,such that <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64859" SRC="img1316.gif" > where <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" > is the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > key (line 19).If it turns out that <IMG WIDTH=43 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64881" SRC="img1320.gif" >, then the search is finished (lines 20-21).Otherwise, <tt>find</tt> calls itself recursivelyto search subtree <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" > (line 23).<P>Consider a search in an <I>M</I>-way search tree.The running time of the second version of <tt>find</tt> is<P> <IMG WIDTH=415 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64844" SRC="img1321.gif" ><P>where <I>h</I> is the height of the tree andregardless of whether the search is successful.If the tree is balanced and <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64143" SRC="img1239.gif" >,then the running time of Program <A HREF="page337.html#progmWayTreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is simply <IMG WIDTH=147 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64891" SRC="img1322.gif" >,where <I>K</I> is the number of keys in the tree.<P><HR><A NAME="tex2html5076" HREF="page338.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5074" HREF="page335.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5070" HREF="page336.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5078" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?