page449.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 62 行
HTML
62 行
<HTML><HEAD><TITLE>Example-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="tex2html6344" HREF="page450.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6342" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6336" HREF="page448.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6346" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014310000000000000000">Example-Binary Search</A></H2><A NAME="secalgsbinsrch"> </A><P>Consider the problem of finding the position of an item in a sorted list.That is, given the sorted sequence <IMG WIDTH=137 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67881" SRC="img1751.gif" > and an item <I>x</I>,find <I>i</I> (if it exists) such that <IMG WIDTH=44 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67887" SRC="img1752.gif" >.The usual solution to this problem is<em>binary search</em><A NAME=32667> </A>.<P>Binary search is a divide-and-conquer strategy.The sequence <I>S</I> is split into two subsequences, <IMG WIDTH=170 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67891" SRC="img1753.gif" >and <IMG WIDTH=230 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67893" SRC="img1754.gif" >.The original problem is split into two subproblems:Find <I>x</I> in <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67897" SRC="img1755.gif" > or <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67899" SRC="img1756.gif" >.Of course, since the original list is sorted,we can quickly determine the list in which <I>x</I> must appear.Therefore, we only need to solve one subproblem.<P>Program <A HREF="page449.html#progexampleo"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the method <tt>binarySearch</tt>which takes four arguments,<tt>array</tt>, <tt>target</tt>, <tt>i</tt> and <tt>n</tt>.This method looks for the position in <tt>array</tt>at which item <tt>target</tt> is found.Specifically, it considers the following elements of the array:<P> <IMG WIDTH=448 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath67879" SRC="img1757.gif" ><P><P><P><A NAME="32691"> </A><A NAME="progexampleo"> </A> <IMG WIDTH=575 HEIGHT=260 ALIGN=BOTTOM ALT="program32688" SRC="img1758.gif" ><BR><STRONG>Program:</STRONG> Divide-and-conquer example--binary search.<BR><P><P>The running time of the algorithm is clearly a function of <I>n</I>,the number of elements to be searched.Although Program <A HREF="page449.html#progexampleo"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> works correctly for arbitrary values of <I>n</I>,it is much easier to determine the running timeif we assume that <I>n</I> is a power of two.In this case,the running time is given by the recurrence<P><A NAME="eqnalgsbs"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation32696" SRC="img1759.gif" ><P><P>Equation <A HREF="page449.html#eqnalgsbs"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is easily solved using repeated substitution:<P> <IMG WIDTH=500 HEIGHT=122 ALIGN=BOTTOM ALT="eqnarray32702" SRC="img1760.gif" ><P>Setting <IMG WIDTH=62 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline67909" SRC="img1761.gif" > gives <IMG WIDTH=193 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67911" SRC="img1762.gif" >.<P><HR><A NAME="tex2html6344" HREF="page450.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6342" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6336" HREF="page448.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6346" 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 + -
显示快捷键?