<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>
/ Z0 I# S% ?6 A G<P ><FONT face="Times New Roman">}//if</FONT></P>
6 e4 y( n. d% A$ I$ @* N" {" Y<P ><FONT face="Times New Roman">return –1;</FONT></P>
* t7 O% Y% x8 `" l) F% R+ z R<P ><FONT face="Times New Roman">}</FONT></P>
6 {( h2 U: X7 K0 `) A ^
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
5 I" a! G0 d' L& i3 P& F<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
" E% {7 C! v/ ^0 J8 B& ]) R; r<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P>
- F" }. c, R9 |+ A5 @. R J+ t<P ><FONT face="Times New Roman">{</FONT></P>
" }4 a0 Q. s0 R1 L<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
0 {! o; K+ O6 N$ N8 u
<P ><FONT face="Times New Roman"> {</FONT></P>
. ~. Y8 d) w: `, h6 y1 l<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
* f% r- ~/ a6 U, k<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
/ V. O' i, {+ |/ B7 j+ F$ p
<P ><FONT face="Times New Roman"> {</FONT></P>
/ J1 h" {7 `5 ~ }; G<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
5 q f7 h+ g& X" N/ q0 a7 |) r<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
: B5 w# Y/ i3 X. `$ x2 C<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
6 E& r \5 V8 _! V7 T: \<P ><FONT face="Times New Roman">}//while</FONT></P>
% a$ `9 c2 k. U e7 |! \# }<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
; X( ~2 h9 f. w; V0 }<P ><FONT face="Times New Roman">}//if</FONT></P>
4 ?( s n1 i/ l: r$ }
<P ><FONT face="Times New Roman">return –1;</FONT></P>
8 D. X- j0 @( v6 F# J! O
<P ><FONT face="Times New Roman">}</FONT></P>
6 k7 X$ }/ A# K0 T! O! ~0 v
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
+ J5 G& ~$ ~8 F<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
% M' G5 e; }6 W( @ r<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>
) ]7 y5 T# W4 i, D<P ><FONT face="Times New Roman">{</FONT></P>
& N& j, D: @& s5 [
<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
( B3 |: O# |3 L+ u3 u7 M, q9 A
<P ><FONT face="Times New Roman"> {</FONT></P>
, L/ E# E# e" n, y+ ~1 f1 M. t9 W
<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
8 i) d7 {* i# i& S# d% k<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
/ b1 [( w, w( g; ^<P ><FONT face="Times New Roman"> {</FONT></P>
; G8 f" \5 X! p5 q8 a& c7 v) G5 y( D<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
. P8 g; `" ~3 c! s2 b, \6 m<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
1 s) e. }5 D N( E# N3 r( w
<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>
: c8 e3 F& b Y" q$ E
<P ><FONT face="Times New Roman">}//while</FONT></P>
# B7 i& |: h- p
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
. z9 p( g2 J! T: l8 p# e/ J3 W C
<P ><FONT face="Times New Roman">}//if</FONT></P>
* V8 m) ]% m w& g<P ><FONT face="Times New Roman">return –1;</FONT></P>
9 K% k( K: T \/ b; P<P ><FONT face="Times New Roman">}</FONT></P>
+ P9 ? K, u- C* }) R: Q<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
9 X- v4 W. u" g- |
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
% d& T$ b3 [# ^8 y) ^; O<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>
4 w: i1 h; ^6 \5 u
<P ><FONT face="Times New Roman">{</FONT></P>
: v2 @2 y: h0 t2 X! z1 J<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
. v# E& a1 S& `- K" ~<P ><FONT face="Times New Roman"> {</FONT></P>
4 ^/ S" N9 E/ y" u<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
0 |. Z, C1 a' m/ ?8 q6 J# F/ w0 ~
<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
- Y: c# T& u2 @7 L! Z<P ><FONT face="Times New Roman"> {</FONT></P>
: K5 ]( [$ o7 \( m2 n0 m<P ><FONT face="Times New Roman"> int middle = (left + right +1) / 2;</FONT></P>
; K6 c/ l4 ]7 P' K+ @; d+ m
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle;</FONT></P>
4 r/ G3 `* d7 x' U% P! k* R/ Z; ^
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
2 R0 Y, C8 y: P<P ><FONT face="Times New Roman">}//while</FONT></P>
; E& C! ?* b, L- }1 _5 _
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
- s9 T! e' T0 k- {2 d# {1 Y<P ><FONT face="Times New Roman">}//if</FONT></P>
8 b5 G4 N v X& S% F% i! X9 _
<P ><FONT face="Times New Roman">return –1;</FONT></P>
* G/ D& K8 y& T1 \, m7 `<P ><FONT face="Times New Roman">}</FONT></P>
* w" _9 d+ o. F" u7 ~
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
1 s* {% s M4 g# C) I7 J" P9 Q<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>
7 m( p7 N# y: G2 O' {6 G Q
<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>
/ h* a; p/ r: |
<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
; G) A9 e" p. v0 _7 ~' H' Z! R' f<P ><FONT face="Times New Roman">if(x > a[middle]) left = middle + 1;<o:p></o:p></FONT></P>
+ R% r7 ]# G" h. G; z<P ><FONT face="Times New Roman"> else right = middle - 1;<o:p></o:p></FONT></P>
/ M) t& L. T* _% \/ B- a6 A/ s
<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>
( \. }6 C# _- T
<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# I, P3 C/ M8 X! x3 x. z# P2 e
<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>
! W/ d9 }; ^( J( k& B7 U<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>
) E D ?! t6 W, ^' t' B& j+ I4 H
<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>
1 D1 q Q0 W( Z0 [. |<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>
" m: m8 K, l) @$ z& r+ p: a3 M
<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>
1 e$ c$ B( [8 x( b. |3 ]: c
<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>
n) I% p, Y7 {4 d2 c9 E3 w<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>
& V6 N% [9 o- G6 `* {4 `& {* ?<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
N0 ?, m1 m2 N" u4 k# z/ S1 M<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>
6 ^# l, z% {7 x; n
<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>
6 m% ^ r& d1 l# f<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>
- H5 N3 c: m: W+ @<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>
9 d' a( t6 |) ]
<P >即:middle > left成立。<o:p></o:p></P>
4 C& i1 G5 M1 F# E0 F; o
<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>
* w) F4 j3 W0 E<P >∴left < middle ≤ right恒成立。<o:p></o:p></P>
. g% f4 _/ i; d, b- e( R<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>
0 c5 G$ {# l( M- k, v9 L<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>
( B* E% o' j; }- {9 ]$ o
<P >∴返回结果正确。<o:p></o:p></P>
5 }; @) t Q, z0 h! j4 T<P >(6)算法6是错误的。<o:p></o:p></P>
" ?5 u! x& V+ z v% J4 W8 s<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>
! H3 X1 \6 S1 r9 s9 Y& j<P >left = middle + 1;<o:p></o:p></P>
* R1 h+ F, h+ l<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>
; ^4 L( i8 z5 n$ N1 Q& ?# d<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>
, e8 x( C" O" a7 M8 i( ]% E
<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>
# J: V$ L4 Q( N% G* I
<P >(7)算法7是错误的。<o:p></o:p></P>
+ t+ g8 q- M) R/ i& ]<P >在循环过程中,一旦出现<o:p></o:p></P>
! z, F8 x) I8 e$ _9 c<P >a
≤ x < a[left + 1],则必进入死循环。<o:p></o:p></P>
8 ?1 W3 x$ X' u, f<P >原因:right值的修改不正确。<o:p></o:p></P>