<P ><FONT face="Times New Roman">public static int binarySearch4(int[] a, int x, int n)</FONT></P>
<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
<P ><FONT face="Times New Roman"> int middle = (left + right) / 2;</FONT></P>
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
) return left;</FONT></P>
5 t9 V& `9 i! \5 W
<P ><FONT face="Times New Roman">}//if</FONT></P>
) x- s5 d) H6 J" a2 f<P ><FONT face="Times New Roman">return –1;</FONT></P>
; i* ~. v9 e# m, X, `2 m: F: q
<P ><FONT face="Times New Roman">}</FONT></P>
+ R( s( i; m7 z8 l/ z& M, A
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
/ X2 d0 i' Y, w% P<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
! C; A* `, j- [<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P>
" e* J- B/ J0 g<P ><FONT face="Times New Roman">{</FONT></P>
; h- B! y6 I' J+ S. N+ R% c0 W4 Z
<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
3 l! W3 M# Z& K; [/ ?2 d<P ><FONT face="Times New Roman"> {</FONT></P>
' Q/ c. N; `9 Y: x, W<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
% W$ l7 x" b: q8 S- z* k$ K1 o1 Q2 D<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
/ m* H v& d- Z' q* E5 i
<P ><FONT face="Times New Roman"> {</FONT></P>
. E) V. p, h0 n- Q<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
3 ^: z. i: G+ Y, J3 l
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
% Q1 _8 u5 m. ]) w5 e<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
$ g7 v H" w, J4 i9 O<P ><FONT face="Times New Roman">}//while</FONT></P>
$ u, A6 I G( I; z1 k
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
4 u/ ?$ f% B, f9 h/ H& V4 m3 a" `<P ><FONT face="Times New Roman">}//if</FONT></P>
0 i+ T% {4 y( D" ^( Q
<P ><FONT face="Times New Roman">return –1;</FONT></P>
7 s3 M! b% l7 H- L7 w# U, y6 Z4 I5 x<P ><FONT face="Times New Roman">}</FONT></P>
9 I- {, h; W- Y
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
# P: c3 y: D9 I- p" |& |6 w5 B
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
4 `. v6 H F- A6 m. c6 u; r<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>
' y$ r! _5 N) s. N<P ><FONT face="Times New Roman">{</FONT></P>
. b0 I) x6 e# I( h2 ?6 Y ~5 t3 B
<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
8 K- l* R) ^) `' t4 C* F" E3 T- D
<P ><FONT face="Times New Roman"> {</FONT></P>
: @! f; g/ ?& j3 X# A<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
% b' g2 k: J$ T9 f' j$ R4 t) d3 @<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
8 W- m4 ~8 b( G4 R
<P ><FONT face="Times New Roman"> {</FONT></P>
! d" E3 ]( l: b, U4 I
<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
, e Y* H( f, u" _. j8 v
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
9 |4 {! q" c5 S5 ]% D' Y, A+ R<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>
# e( T6 ^ q3 r* {4 H9 N( |<P ><FONT face="Times New Roman">}//while</FONT></P>
m9 ^. v, _, F$ [3 L1 L2 L2 U<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
( m* K' P* ]0 `" b" _
<P ><FONT face="Times New Roman">}//if</FONT></P>
O6 n4 w( M( D/ S% L<P ><FONT face="Times New Roman">return –1;</FONT></P>
( C& p3 |/ z+ i( e! E( m/ E! y<P ><FONT face="Times New Roman">}</FONT></P>
, C2 C, g4 Z2 j" _) \% ^ L$ _/ N<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
, B# P5 u! \7 o! F# q/ G
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
: e1 v6 K |+ J" e4 j, S; t<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>
- k5 P0 q8 x# a<P ><FONT face="Times New Roman">{</FONT></P>
. U4 P9 ~9 o% T. J/ x) h$ U
<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
4 O3 L. z0 T# q. v7 i4 U! j<P ><FONT face="Times New Roman"> {</FONT></P>
( Z( Z* Y# K" ^2 ]4 h; |<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
2 _: l6 j, U2 S7 [<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
3 ?% M) q' e* i- C; U$ m# N9 h<P ><FONT face="Times New Roman"> {</FONT></P>
6 }7 }/ P, W$ ~% ]% R
<P ><FONT face="Times New Roman"> int middle = (left + right +1) / 2;</FONT></P>
6 t9 X# B: z4 J2 L4 F9 i! Y7 m% `<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle;</FONT></P>
$ c' h0 y) J, C% F, t% ~; c# e
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
6 b" D. x9 u* q. Y<P ><FONT face="Times New Roman">}//while</FONT></P>
3 r) w- k1 m: [7 l
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
4 W1 z" d- N" ?5 h
<P ><FONT face="Times New Roman">}//if</FONT></P>
/ A* F1 o4 E s9 ]' j" h<P ><FONT face="Times New Roman">return –1;</FONT></P>
% g7 A) J# s1 g<P ><FONT face="Times New Roman">}</FONT></P>
$ f& A% y3 B8 u- b+ G2 A2 }& n
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
6 x" X6 \ {* `5 M9 G+ d/ r% _<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>
5 h+ Z& C: [# S7 _, m
<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>
- j2 q, _3 n# ]/ K2 K' X; k<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
, }# ~& W" |+ l" N. x1 e<P ><FONT face="Times New Roman">if(x > a[middle]) left = middle + 1;<o:p></o:p></FONT></P>
; T" w0 Y! ~. P6 o<P ><FONT face="Times New Roman"> else right = middle - 1;<o:p></o:p></FONT></P>
3 D/ B, X- E( u" V. d
<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>
0 O0 a8 s, P( {1 g0 K) L<P >当<FONT face="Times New Roman">n</FONT>≥<FONT face="Times New Roman">2</FONT>时,如果条件<FONT face="Times New Roman">x = a[n-1] </FONT>且<FONT face="Times New Roman"> a[n-2] </FONT>≠<FONT face="Times New Roman"> a[n-1]</FONT>成立,则必将在某一步之后出现<FONT face="Times New Roman">x = a[left +1]</FONT>,导致永远不会出现<FONT face="Times New Roman">x = a[middle]</FONT>的情形,算法最终在<FONT face="Times New Roman">x = a
</FONT>时结束循环,导致错误地返回<FONT face="Times New Roman">-1</FONT>。<o:p></o:p></P>
, o% Y4 p9 B) I U% ?- K<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>
0 ^5 x7 b( Q; P# q% J
<P >原因:循环结束条件错误,应改为<FONT face="Times New Roman">left <= right</FONT>。每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改也不正确。<o:p></o:p></P>
# R6 C7 r0 r0 Y" y5 L1 V) u$ B<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>
& [1 b7 K7 ?2 h @# z' E<P >除了有与算法<FONT face="Times New Roman">2</FONT>相同的错误,另外当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,必然进入死循环。<o:p></o:p></P>
9 H# D; ?# q. V4 Z6 m
<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>
4 P' D& I z' M6 U8 _<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>
2 D, V0 O3 ]% x: G& m) @<P >如果在循环过程中出现<FONT face="Times New Roman">left = right – 1</FONT>情况,算法即进入死循环。例如<FONT face="Times New Roman"> x</FONT>≥a[n-2]条件成立时,即必然进入死循环。<o:p></o:p></P>
2 H( k! j; T1 b }7 ]3 R<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
3 Y" F" W. ^/ g
<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>
# v: B. O4 X: f; q8 ^<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>
: P6 B6 F; I7 ?/ n, W5 N$ q<P >当<FONT face="Times New Roman">n</FONT>≥<FONT face="Times New Roman">2</FONT>时,在循环结束前有<FONT face="Times New Roman">x</FONT>≥a[0]且left < right,<o:p></o:p></P>
$ S E! f: [0 L" f
<P >∴<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [left + (right –1) + 1 +1] / 2 </FONT>≥ (2left + 2) / 2 = left + 1,<o:p></o:p></P>
3 E5 q; U" h# u% @
<P >即:middle > left成立。<o:p></o:p></P>
& P; z- H/ K0 G# z
<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>
( X2 P9 V3 {9 f# D4 ^7 ?
<P >∴left < middle ≤ right恒成立。<o:p></o:p></P>
7 M( n1 w- U* g; ~% u: ^<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>
7 ?$ A- c+ ?* S# Y N<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>
2 W: u W N3 V+ [4 @- ^
<P >∴返回结果正确。<o:p></o:p></P>
T6 m! q C" ~: Y- O; L$ b" x6 x7 L
<P >(6)算法6是错误的。<o:p></o:p></P>
) y/ `3 u" G* V
<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>
s. r! I2 d/ T1 e<P >left = middle + 1;<o:p></o:p></P>
( L. B) Q0 I3 a; H* T; x e<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>
e' b, F2 P4 R' [4 b- F0 L! d<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>
* S% a/ H4 H/ T" a1 _; s& ~0 M% W9 c
<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>
+ t) W* b% F* V7 O& P<P >(7)算法7是错误的。<o:p></o:p></P>
. v& g9 q) D0 |, j. `
<P >在循环过程中,一旦出现<o:p></o:p></P>
' M; `5 V- x6 G5 U c" N3 u<P >a
≤ x < a[left + 1],则必进入死循环。<o:p></o:p></P>, M- d: \: ]. v; {# A' a2 v
<P >原因:right值的修改不正确。<o:p></o:p></P>