<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>
; s0 O2 m. L4 E5 `<P ><FONT face="Times New Roman">}//if</FONT></P>
0 a6 h& ]' V5 b4 o- u<P ><FONT face="Times New Roman">return –1;</FONT></P>
7 y) Z2 G" c+ V& O6 j2 E<P ><FONT face="Times New Roman">}</FONT></P>
/ s7 O# O% T; V v3 U. e7 p2 h4 x<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
5 U! K+ ~7 a, O5 ~" \6 H7 N/ j( U
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
% m6 H% u! n3 n& @2 _0 _3 T
<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P>
& A; a+ m1 Y3 E) F5 t<P ><FONT face="Times New Roman">{</FONT></P>
. r. O6 c9 Z1 L: s5 J- h7 K! q<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
6 ~" m0 U& @& h; F, T' n1 u<P ><FONT face="Times New Roman"> {</FONT></P>
: U% t! B( {9 \( ]- D f<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
) |' I9 a; M% Y. }( A- ~
<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
+ P$ z8 D: n7 I# X: m3 D3 p+ I8 X
<P ><FONT face="Times New Roman"> {</FONT></P>
4 s0 O! {3 t! H; f+ |& a. S<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
2 ]+ }! n- x6 g8 j8 z3 O2 W( S<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
0 Q. I5 t7 [6 Y9 z
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
. k' Z* `* Z% S+ P6 L
<P ><FONT face="Times New Roman">}//while</FONT></P>
( N8 Z6 ?! \( ~# o5 n" r! S<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
4 x4 |4 j6 L7 O/ o' Y7 e
<P ><FONT face="Times New Roman">}//if</FONT></P>
( w/ P* F5 T5 ^
<P ><FONT face="Times New Roman">return –1;</FONT></P>
! e" K/ I. q. c1 g/ @<P ><FONT face="Times New Roman">}</FONT></P>
; k6 q$ ^0 q: `' g" Y+ X
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
! N$ @# [2 v; S+ w$ l! I: L<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
3 I- b7 b: P2 }/ L1 z
<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>
0 q/ N! q$ T4 e5 E# s# V- F
<P ><FONT face="Times New Roman">{</FONT></P>
' H# e' O0 z% e, V' N<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
! i- q5 D: ^3 {" l1 a. w, C3 c
<P ><FONT face="Times New Roman"> {</FONT></P>
2 q2 x6 o5 h: N
<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
" U+ n, o' n# X( @0 G
<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
* t& [* z7 T% l/ d
<P ><FONT face="Times New Roman"> {</FONT></P>
! @' Q' x1 r: }) |<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
3 [7 w2 k5 ]0 {: Q+ K* B& }$ ]
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
0 }" d7 y! b4 u8 h<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>
" j- i) u, c& P9 i; A<P ><FONT face="Times New Roman">}//while</FONT></P>
/ n. N" p. ~" ]! x, o/ Z
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
* Y* I+ ~" Y+ V; J# \' S4 J
<P ><FONT face="Times New Roman">}//if</FONT></P>
4 |4 \4 K" `, y8 l9 Z% K<P ><FONT face="Times New Roman">return –1;</FONT></P>
; D E( H1 F$ I
<P ><FONT face="Times New Roman">}</FONT></P>
( t9 ^: u1 |8 B% i2 D' q<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
3 Z# e! M9 T8 t. X8 _
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
; f% O4 d4 O6 n. ]( B% n
<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>
( y3 k( t8 P$ { N8 k9 Y4 \2 @
<P ><FONT face="Times New Roman">{</FONT></P>
( Q7 u: T: w, N2 f8 {; c% |<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
) e& w: s) W1 _9 R<P ><FONT face="Times New Roman"> {</FONT></P>
" {( z# j. l7 d4 ~0 e8 K
<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
% H- d2 i0 M: b. i* s<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
6 I) \5 ~1 S2 }1 V0 L# w: h<P ><FONT face="Times New Roman"> {</FONT></P>
2 E. V& ~& O4 Y, ~& U* F6 U<P ><FONT face="Times New Roman"> int middle = (left + right +1) / 2;</FONT></P>
6 I& x& u* v. Y$ v
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle;</FONT></P>
$ V$ Z$ Z5 a, N0 A$ t' H<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
* G c! y6 s) F<P ><FONT face="Times New Roman">}//while</FONT></P>
( C7 N" E" A( B; t& f; j6 Q<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
4 ?2 f: p. ?+ `5 Y' t% M0 b6 Y1 O) O<P ><FONT face="Times New Roman">}//if</FONT></P>
8 M4 f4 q! U) G$ ^' ?% Q
<P ><FONT face="Times New Roman">return –1;</FONT></P>
# B3 m7 K/ o5 \<P ><FONT face="Times New Roman">}</FONT></P>
. ?( \& I8 p3 D<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
1 }# D* i- c5 N& a+ O! H<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>
) Q9 @# Q" B' n, a<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>
* c& g3 Y- _3 g% E$ W N<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
9 \% [: C( {! P5 c h5 @: X- O<P ><FONT face="Times New Roman">if(x > a[middle]) left = middle + 1;<o:p></o:p></FONT></P>
+ e: w J% l: I2 b
<P ><FONT face="Times New Roman"> else right = middle - 1;<o:p></o:p></FONT></P>
1 l9 H) E5 d# W9 B* ]: B' ~* W/ p<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>
! M9 B" K* C. V7 H9 O4 ^<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>
0 Y9 _ n/ ^/ r
<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>
6 U/ R) k; o! m4 h
<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>
* `$ Y5 t, @3 z( c6 {<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>
- d3 m H9 p8 N: e b9 @
<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>
0 x& l9 L+ U0 i U) g/ ]5 O5 g<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>
/ c+ Y( O4 y0 o2 I' Q- g<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>
, Q( `' T7 f; L$ R* l<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>
( ~" J# R1 t! p<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
$ }4 s: F! ?6 D/ p<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>
, K: Y" w/ t# G
<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>
. \2 S# X# r$ e6 A0 k<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>
, v. L) T3 E& n) z- l<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>
* X8 U) D2 N; Q" A! u
<P >即:middle > left成立。<o:p></o:p></P>
$ ?, t9 [ B, _1 ? {<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>
4 g) E7 ]$ k6 @3 c" [( X$ [! J4 J
<P >∴left < middle ≤ right恒成立。<o:p></o:p></P>
7 z, r; y2 n d# B/ q* f! a9 J, c
<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>
+ ~! r: M# _: u5 f
<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>
4 W9 M2 h' S- ], J; L<P >∴返回结果正确。<o:p></o:p></P>
+ ~% x0 g4 K, [+ T5 c<P >(6)算法6是错误的。<o:p></o:p></P>
7 W5 C* s' p' }! i+ q9 ]7 }<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>
" c8 U. ^2 |" N4 g<P >left = middle + 1;<o:p></o:p></P>
6 S4 G: o, U+ v
<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>
l2 `7 X9 Y B# o' t- W, r% x$ K<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>
+ ~- g, \& L' q* {8 @7 Y8 B
<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>
r$ R9 q* M5 u. I3 M% [<P >(7)算法7是错误的。<o:p></o:p></P>
5 d* @' I- |; s @
<P >在循环过程中,一旦出现<o:p></o:p></P>
; B w, x6 }, \/ K9 K
<P >a
≤ x < a[left + 1],则必进入死循环。<o:p></o:p></P>
% `6 K# [* ^7 S9 `" D; y<P >原因:right值的修改不正确。<o:p></o:p></P>