<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>
) C" a: d" ?% u7 j' v$ S9 a<P ><FONT face="Times New Roman">}//if</FONT></P>
; r# w v3 @; }8 g; I/ Y2 T<P ><FONT face="Times New Roman">return –1;</FONT></P>
9 V8 I6 |3 O5 y& o' U2 T6 e2 c8 ~
<P ><FONT face="Times New Roman">}</FONT></P>
- l V$ A0 s/ N" w
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
6 L$ s# _6 z- ~8 s<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
; ]- ?; U$ J7 @, r% T4 `6 M3 j1 U<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P>
* I$ m! ^; z- L* Q6 ? v
<P ><FONT face="Times New Roman">{</FONT></P>
6 i) P ~, `2 J* `6 q* @; |<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
5 `0 ]: p, j) ^' |5 f/ L% v
<P ><FONT face="Times New Roman"> {</FONT></P>
% t9 \' p! {/ S9 S9 ?% g4 h- v2 @
<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
$ I4 y: \0 l) d# \' X; Z- }
<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
7 x. Q" C* z# l
<P ><FONT face="Times New Roman"> {</FONT></P>
* {1 o+ h$ A' V a- G<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
$ ]+ e: O, j; |# a6 ^
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
8 C( @- X6 a+ S6 i: l
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
3 u; F* i, r9 g! X% k
<P ><FONT face="Times New Roman">}//while</FONT></P>
; w" b! ]0 Z$ _' H+ U
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
+ _6 m9 |7 n" O<P ><FONT face="Times New Roman">}//if</FONT></P>
5 [+ _7 C- |) d5 Y8 h
<P ><FONT face="Times New Roman">return –1;</FONT></P>
& F- @* Y4 n7 J: R, H
<P ><FONT face="Times New Roman">}</FONT></P>
6 X$ o4 J6 D( [2 q- M
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
3 B# w S1 s1 `3 i6 Y- r) ^
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
9 _# H4 c* q/ Y4 O<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>
. R! b8 i( K5 o<P ><FONT face="Times New Roman">{</FONT></P>
. q: p- _: L9 r* P<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
) ]3 C2 @# L0 O1 D2 s5 q" B<P ><FONT face="Times New Roman"> {</FONT></P>
- [! s: ]9 @" G
<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
% I6 ]$ V) K' F) K& ?- y' Z( R
<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
4 [* e1 r+ i. [: k. z- y7 `4 x# Y5 {) B<P ><FONT face="Times New Roman"> {</FONT></P>
; D s( N& u" r6 z# W1 j<P ><FONT face="Times New Roman"> int middle = (left + right + 1) / 2;</FONT></P>
8 H5 v' ~0 x. b( x
<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle - 1;</FONT></P>
( k- ]' h( m4 J* w: ]3 e; E! P<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>
9 l5 S9 a2 ? n- P) t; x<P ><FONT face="Times New Roman">}//while</FONT></P>
4 h0 @6 c$ Z3 `" E9 W0 j<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
* K# J" i8 D; a F* T<P ><FONT face="Times New Roman">}//if</FONT></P>
2 |; }$ b I( a0 C8 f8 u
<P ><FONT face="Times New Roman">return –1;</FONT></P>
; Y7 _ u9 e* L& ]$ W<P ><FONT face="Times New Roman">}</FONT></P>
# f- R. f+ W4 p& C
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
) z( _5 |- V& w, T. |* j* P
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
( H4 A" _" s- Q; k3 I) @0 c<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>
! L2 K) ~# Z8 @! W1 ~% \<P ><FONT face="Times New Roman">{</FONT></P>
8 D* q; p8 o$ \5 }6 N$ g: g5 n<P ><FONT face="Times New Roman"> if(n > 0 && x >= a[0])</FONT></P>
& O# t/ {8 R3 B) Z<P ><FONT face="Times New Roman"> {</FONT></P>
1 b+ }. D w9 s, s8 Z& v<P ><FONT face="Times New Roman"> int left = 0, right = n-1;</FONT></P>
* [3 C' X* l% T O/ B) O* r5 d<P ><FONT face="Times New Roman"> while(left < right)</FONT></P>
9 p/ Q. F3 B9 u$ x) o3 n<P ><FONT face="Times New Roman"> {</FONT></P>
4 x( N& q2 r' [/ C3 h& f2 @<P ><FONT face="Times New Roman"> int middle = (left + right +1) / 2;</FONT></P>
, Y: o! _; _# W9 F/ a k; v5 H<P ><FONT face="Times New Roman">if(x < a[middle]) right = middle;</FONT></P>
- q: p, \. s/ ^5 H
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
) j, Y# Q% @4 Q* I$ q+ a% c. |' ~
<P ><FONT face="Times New Roman">}//while</FONT></P>
& s; @- Z+ K$ Z8 E<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
1 _* d2 z$ w1 {/ f
<P ><FONT face="Times New Roman">}//if</FONT></P>
5 z. ^5 F2 ~; Y: l<P ><FONT face="Times New Roman">return –1;</FONT></P>
S8 O' I2 k; q9 T5 N
<P ><FONT face="Times New Roman">}</FONT></P>
6 k' R9 K! ~2 V7 c5 l- u* y+ \
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
- P6 O b" [. a
<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>
" {- Q7 J; n1 N+ Z# F5 Y3 v<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>
5 H% C' C( _: D' V
<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
" S- J7 G3 k {0 R- S
<P ><FONT face="Times New Roman">if(x > a[middle]) left = middle + 1;<o:p></o:p></FONT></P>
O. {- R' n8 d% j' e
<P ><FONT face="Times New Roman"> else right = middle - 1;<o:p></o:p></FONT></P>
: B, \7 G6 S$ A8 T0 ^* j9 r
<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>
7 \- W& e- ]2 d$ H8 U
<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 {" U. R) y6 ^: k<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>
+ h1 z1 ]6 I& \8 E" _! u% c9 v<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>
. a9 L; }# e) [# J1 h0 A<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>
" v2 J* s0 b5 S6 g% y, n9 d
<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>
6 h. E3 }- z( F, ~
<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>
) ^$ c3 W1 F3 I, E5 j ]4 E. t
<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>
7 Q' Y% V) _5 p: B8 T- Y! z<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>
1 c5 v9 B; ?& N0 K; j5 s% v3 M
<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
& a3 d0 }; Y: Q# |* D
<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>
9 O- }. ?# b* v8 G6 e$ N9 i<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>
) s/ n* S$ [5 S1 {<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>
3 f0 j$ g4 u8 `" ?, U<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>
! Y6 b# Y4 H8 L0 n7 E u, g( y<P >即:middle > left成立。<o:p></o:p></P>
* L2 S" V" K: U4 r& N" L2 N$ U# u
<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>
5 s9 u- r0 v+ N! s! [! n$ W
<P >∴left < middle ≤ right恒成立。<o:p></o:p></P>
# x. c# J, ]% S9 M2 \<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>
9 g; W4 f& m" W: ?1 i N4 H* y<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>
( z( C$ q c/ A6 F! ^& T$ K<P >∴返回结果正确。<o:p></o:p></P>
& c+ y M: o/ z5 m% z- K<P >(6)算法6是错误的。<o:p></o:p></P>
9 p$ C* R$ Q% M. r7 O
<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>
8 c# @5 d$ S0 T6 R. \- A
<P >left = middle + 1;<o:p></o:p></P>
* a% d8 v* o. d, m3 {6 y2 @
<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>
( ^3 C4 E1 A- v: U3 p8 h; m
<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>
* D* V( h. z6 f8 H4 |
<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>
5 ~; S1 A% q8 X# c2 `0 A+ j
<P >(7)算法7是错误的。<o:p></o:p></P>
' |" C: I* F) e( D<P >在循环过程中,一旦出现<o:p></o:p></P>
9 N _" Q" i, S; Z+ C. M
<P >a
≤ x < a[left + 1],则必进入死循环。<o:p></o:p></P>
, z- H" S3 `9 s$ e% e0 y% z<P >原因:right值的修改不正确。<o:p></o:p></P>