page191.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 63 行
HTML
63 行
<HTML>
<HEAD>
<TITLE>Locating Items in an Array-Binary Search</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4277" HREF="page192.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page192.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4275" HREF="page189.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page189.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4269" HREF="page190.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page190.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4279" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4280" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION008212000000000000000">Locating Items in an Array-Binary Search</A></H3>
<P>
Given a sorted array of items,
an efficient way to locate a given item
is to use a <em>binary search</em><A NAME=10752> </A>.
The <tt>FindOffset</tt> member function of the <tt>SortedListAsArray</tt> class
defined in Program <A HREF="page191.html#progsorted2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page191.html#progsorted2c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> uses a binary search
to locate an item in the array which matches a given item.
<P>
<P><A NAME="11050"> </A><A NAME="progsorted2c"> </A> <IMG WIDTH=575 HEIGHT=372 ALIGN=BOTTOM ALT="program10756" SRC="img851.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img851.gif" ><BR>
<STRONG>Program:</STRONG> <tt>SortedListAsArray</tt> Class <tt>FindOffset</tt> Member Function Definition<BR>
<P>
<P>
The binary search algorithm makes use of a <em>search interval</em>
to determine the position of an item in the sorted list.
The search interval is a range of array indices
in which the item being sought is expected to be found.
The initial search interval is <IMG WIDTH=99 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline61954" SRC="img852.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img852.gif" >.
The interval is iteratively narrowed by comparing the
item sought with the item found in the array at the middle
of 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 smaller
than any item in the list because this case requires
two comparisons in each iteration of the binary search loop.
In the worst case, <IMG WIDTH=72 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61956" SRC="img853.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img853.gif" > iterations are required.
Therefore, the running time of the <tt>FindOffset</tt> function is
<IMG WIDTH=273 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61958" SRC="img854.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img854.gif" >,
where <IMG WIDTH=84 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61960" SRC="img855.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img855.gif" > represents the running time required to compare
to <tt>Object</tt> instances.
If we assume that <IMG WIDTH=137 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61962" SRC="img856.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img856.gif" >,
then the total running time is simply <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" >,
where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61308" SRC="img709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img709.gif" >.
<P>
<HR><A NAME="tex2html4277" HREF="page192.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page192.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4275" HREF="page189.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page189.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4269" HREF="page190.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page190.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4279" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4280" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?