📄 page193.html
字号:
<HTML><HEAD><TITLE>Locating Items in an Array-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="tex2html3432" HREF="page194.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3430" HREF="page191.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3424" HREF="page192.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3434" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007212000000000000000">Locating Items in an Array-Binary Search</A></H3><P>Given a sorted array of items,an efficient way to locate a given itemis to use a <em>binary search</em><A NAME=10118> </A>.The <tt>findOffset</tt> method of the <tt>SortedListAsArray</tt> classdefined in Program <A HREF="page193.html#progsortedListAsArrayc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> uses a binary searchto locate an item in the array which matches a given item.<P><P><A NAME="10450"> </A><A NAME="progsortedListAsArrayc"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program10122" SRC="img804.gif" ><BR><STRONG>Program:</STRONG> <tt>SortedListAsArray</tt> class <tt>findOffset</tt> method.<BR><P><P>The binary search algorithm makes use of a<em>search interval</em><A NAME=10132> </A><A NAME=10133> </A>to determine the position of an item in the sorted list.The search interval is a range of array indicesin which the item being sought is expected to be found.The initial search interval is <IMG WIDTH=107 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline61311" SRC="img805.gif" >.The interval is iteratively narrowed by comparing theitem sought with the item found in the array at the middleof the search interval.If the middle item matches the item sought,then we are done.Otherwise, if the item sought is less than the middle item,then we can discard the middle item and the right half of the interval;if the item sought is greater than the middle item,we can discard the middle item and the left half of the interval.At each step,the size of the search interval is approximately halved.The algorithm terminates either when the item sough is found,or if the size of the search interval becomes zero.<P>In the worst case,the item sought is not in the sorted list.Specifically, the worst case occurs when the item sought is smallerthan any item in the list because this case requirestwo comparisons in each iteration of the binary search loop.In the worst case, <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61313" SRC="img806.gif" > iterations are required.Therefore, the running time of the <tt>FindOffset</tt> method is <IMG WIDTH=287 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61315" SRC="img807.gif" >,where <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61317" SRC="img808.gif" > and <I>T</I><I>GT</I> represents the running times required to comparetwo <tt>ComparableObject</tt> instances.If we assume that <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61321" SRC="img809.gif" > and <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61323" SRC="img810.gif" >,then the total running time is simply <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >,where <IMG WIDTH=78 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61037" SRC="img743.gif" >.<P><HR><A NAME="tex2html3432" HREF="page194.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3430" HREF="page191.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3424" HREF="page192.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3434" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -